math problem

kai · #1 10-12-2007, 01:11 AM

A tow-pan balance and 16 coins of different weights are given. What is the fewest number of usages of the balance needed to determine the heaviest coin, the second heaviest coin and the third heaviest coin?

How many can you do it in? I can't think of anything better then a pretty brute technique that does it in 23.

Sholar · #2 10-12-2007, 01:57 AM

<font color="white">First figure out the heaviest one just doing a binary search: 15 weighings. The key point is that the second heaviest coin is one that was eliminated by the winner at some point; there are only four choices (the coins which lost directly to the ultimate winner; we also have a pool of 10 coins which contains the second and third place guys). So two more weighings can determine the second heaviest. Now do the same thing for third place...in the worst case, the second place coin from the original bracket wins. Now there are 5 contenders for third place (two from the second place pool and three that were eliminated in the original pool). This requires four more weighings. So 21 or better. It looks like 17 is simplest for top two; can one do better than 21 for the top three?</font>

skates · #3 10-12-2007, 02:16 AM

I can't think of a better method off-hand than Sholar's. However, unless I misunderstood, his method takes 22 measurements, not 21. (Second place coin has 4 choices, which takes 3 measurements, not 2). Worst case scenario leaves 5 contendors as noted for third which takes 4 measurements. I have 15 + 3 + 4. I don't do CSE, but since we're assuming the weights are all distinct, I think this is optimal.

kai · #4 10-12-2007, 10:29 AM

Thats the method I had in mind, I thought it was 15 for the binary to find heaviest. Then there are 4 contenders for second place so that takes 3. But the third heaviest could have been eliminated by the heaviest or the second heaviest. In the worst case where the two heaviest coins met at the end you will have all the non second place coins that the heaviest eliminated (3) and all the coints the second place eliminated (3) which will take 5 moves to sort through. Therefore I think this method takes 23.

So whats your method skates?

kurto · #5 10-12-2007, 10:57 AM

[ QUOTE ]
First figure out the heaviest one just doing a binary search: 15 weighings. The key point is that the second heaviest coin is one that was eliminated by the winner at some point;

[/ QUOTE ]

Umm... correct me if I'm wrong here... but this doesn't always work.

If on the first trial, you compare the heaviest and the second heaviest... at the end of the first 15 weighings, you will only know which coin is the heaviest.

If you luck was bad and you had the 2nd heaviest when you started the second trial, it would take 14 weighings doing this method to find the next heaviest.

Worst case scenario... you could have to do 15+14+13+12= 54 weighings to determine the top 4 if, each time you start the trials, you begin with the heaviest.

Or am I missing something?

Silent A · #6 10-12-2007, 11:04 AM

[ QUOTE ]
In the worst case where the two heaviest coins met at the end you will have all the non second place coins that the heaviest eliminated (3) and all the coints the second place eliminated (3) which will take 5 moves to sort through. Therefore I think this method takes 23.

[/ QUOTE ]

When you weigh off the four coins to find out who is second, you can eliminate one of the coins. For example:

If the four contenders are: A, B, C, and D

weighing 1 = A vs B (assume it's A)
weighing 2 = C vs D (assume it's C)
weighing 3 = winner of 1 (A) vs. winner of 2 (C) (assume it's A)

However, the coin that lost to the loser of #3 (coin D in this case) can't be the #3 coin because it's lighter than the overall winner AND at least 2 of the 2nd place contenders.

I'm pretty sure the answer is 22.

jay_shark · #7 10-12-2007, 11:21 AM

Just label the coins randomly 1,2,3,...,15,16 . Treat it like a tournament with 8 coins on one side of the bracket and 8 coins on the other . As usually the pairings are done randomly according to their number .

ie , one side is (1,2),(3,4),(5,6),(7,8) . The other side can be paired off similarly. So there are 15 possible matches in total to determine the heaviest i.e,8+4+2+1=15 .

jay_shark · #8 10-12-2007, 11:40 AM

So what we do is take the 3 opponents from the loser finalist and pair them off with each other . So we have 3 possible choices to determine the second heaviest from that side of the bracket . Now we take this coin and pair it off with the 3 losers on the winners side of the bracket . Now we have to compare the heaviest of the 6 weighings with the loser finalist and we get 22 in total . Best case scenario is that it can be done in 21 attempts but not always !

Sholar · #9 10-12-2007, 12:18 PM

[ QUOTE ]
I can't think of a better method off-hand than Sholar's. However, unless I misunderstood, his method takes 22 measurements, not 21. (Second place coin has 4 choices, which takes 3 measurements, not 2). Worst case scenario leaves 5 contendors as noted for third which takes 4 measurements. I have 15 + 3 + 4. I don't do CSE, but since we're assuming the weights are all distinct, I think this is optimal.

[/ QUOTE ]

That's right. Weights possibly being equal would only help.

Silent A · #10 10-12-2007, 12:37 PM

[ QUOTE ]
So what we do is take the 3 opponents from the loser finalist and pair them off with each other . So we have 3 possible choices to determine the second heaviest from that side of the bracket . Now we take this coin and pair it off with the 3 losers on the winners side of the bracket . Now we have to compare the heaviest of the 6 weighings with the loser finalist and we get 22 in total . Best case scenario is that it can be done in 21 attempts but not always !

[/ QUOTE ]

There are 4 possible 2nd place coins, and up to 5 possible 3rd place coins.