math problem
 

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.

Re: math problem
 

<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>

Re: math problem
 

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.

Re: math problem
 

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?

Re: math problem
 

[ 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?

Re: math problem
 

[ 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.

Re: math problem
 

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 .

Re: math problem
 

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 !

Re: math problem
 

[ 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.

Re: math problem
 

[ 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.

Re: math problem
 

[ QUOTE ]

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

[/ QUOTE ]

I realized that after posting but didn't have time to edit my post.

This problem was among some other really difficult problems, so it just seems like the answear we came up with here is not good enough. If I find out that there is a better way I'll let you all know.

Re: math problem
 

Edit: don't bother reading. The following is all wrong.

I think I solved it in fewer than 23. Here is my solution in white: <font color="white"> Let’s divide the coins into 4 brackets.

1-4, 5-8, 9-12, 13-16
Weight 1v2, heaviest advances against 3, heaviest advances against 4,
repeat for 5-8, 9-12, and 13-16.

12 moves later, we have a final 4. Let's renumber them for simplicity. The heaviest in each group is the lowest number.

Let's do a 2 round (3 move) playoff between the final 4, and renumber all the brackets so that the playoffs went like this:
1&gt;5
9&gt;13

1&gt;9

1 is now heaviest of them all.
14-16 are completely eliminated.

The 9-12 bracket will have exactly 1 more coin that's not eliminated. The one that lost to 9.

Same with the 5-8 bracket.

So we still have 8 coins eligible for 2nd or3rd place (coin #1 is the heaviest, so it is obviously not included).

We are the same 15 moves in as the binary system so far.

The only ones eligible for 2nd are the coins that lost directly to #1. That is at most 5 coins (probably less depending on how the 1-4 bracket went).

Let's renumber so that the alive coins are 2,3,4,5,6,9,10,13

To clarify, 2,3,4, 5, and 9 are the only ones eligible for 2nd heaviest.

Weight 5 vs 9. This will also eliminate either 6 or 10 in the running for 3rd.

We get the least information from bracket 1 if 1 went 3-0, so let’s assume that. Any other scenario can be solved if this one can this way (I think?).

Weigh 2vs3 and then then 4 vs the winner of 5 and 9.

Weigh the 2 winners, and we have 2nd.

We are now 18 moves in, and have a 1st and 2nd.
Let’s renumber again so that 5 beat 9, so 10 was eliminated. 2 and 3 are identical right now. Let’s renumber so that 2 beat 3.

We have multiple possibilities now.

1) 4 beat 5.
1a) 2 beat 4.
1b) 4 beat 2.

2) 5 beat 4.
2a ) 2 beat 5
2b) 5 beat 2.

1a gives us 1 &gt; 2, with 3, 4, and 5 eligible for 3rd. = solution in 20 moves
1b gives us 1&gt;4, with 2, 3 and 5 eligible for 3rd = solution in 20 moves

2a gives us 1&gt;2 with 3,5 and 9 eligible for 3rd = solution in 20 moves
2b gives us 1&gt;5 with 2, 4 and 9 eligible for 3rd = solution in 20 moves

Edit: In all cases 13 is still eligible for 3rd, so we will have 4 contenders for 3rd instead of 3 each time = solution in 21 instead of 20.
</font>

Re: math problem
 

Crap, just realized I neglected at least one of the 3rd place contenders. I still think my method will come up with a solution better than 23 though. Working it out now.

Edit: I think my only mistake was neglecting #13 which adds 1 more move to my solution at the end. It should still work.

Re: math problem
 

BAH. I'm stupid and screwed up. I eliminated 11 and 12 as well, so that adds 2 more moves = I came up with a solution for 23.

Re: math problem
 

Is there a good way to show that 22 is the best possible, i.e., the minimum number required in the worst case?

Re: math problem
 

On a similar note, if you're trying to rank all the coins, it's not too hard to show that an upper bound for the number of weighings necessary is given by F(1)=0 F(n+1)=F(n)+log base 2 rounded up(n+1). Can anybody do better than this, or prove it's optimal?

Re: math problem
 

Pretty sure it's 21. Do the standard 16-coin bracket to get the heaviest coin A (15 weighings).

Now, weigh the first coin A beat (1) vs. the second coin A beat (2). Winner vs. the 3rd coin A beat (3). Winner vs. the 4th coin A beat (4). The winner is the second heaviest coin B. (18 weighings)

Now there are at most 4 contenders for the 3rd coin C. If 1 is B, then only the 3 coins that lost to it for 2nd can be 3rd (+2 weighings). If 2 is B, then 1,3,4 + the coin 2 beat in the bracket can be C (+3 weighings). If 3 is B, then only 2,4 + the two coins B beat in the bracket can be C (1 is eliminated because it lost to A,B,2). If 4 is B, then only 3 + the three coins B beat in the bracket can be C (+ 3 weighings).

So 18 + max 3 = 21. Interestingly, it takes 42 pieces of information (A&gt;15 coins, B&gt;14 coins, C&gt;13 coins), which is 21*2, to rank the top 3, although I have no idea if this is just a pure coincidence. Edit: it is.

The non-bracket weigh-off for 2nd, in that specific order, controls the possibilities for 3rd better, because in the worst case (opposite side of the bracket from A has B), you've eliminated TWO contenders for 3rd from the A side of the bracket, instead of just 1 by doing a bracket-weighoff for 2nd.

Re: math problem
 

Nice.

Re: math problem
 

TomCowley is correct. The non-bracket weigh-off for second is more efficient and the answer is 21. Can someone give me a purely mathematical explanation of WHY the non-bracket weigh-off becomes more efficient? I can demonstrate it to myself, but I'm asking for the conditions that make it so, and how we can intuitively see this as being optimal.

The difference in this case is that using a non-bracket weigh-off leaves a worst case scenario of 4 contenders for 3rd place as opposed to the 5 contenders given by a bracket weigh-off.

Re: math problem
 

I'm not sure that there's really a general principle at work here. One point is that after the initial bracket, one already knows the potential second and third place coins. Finding the second place coin (from 4) will take 3 trials, whether one does it bracket style or not; but with so few contenders, only one coin is eliminated from being the 3rd place one if the 2nd place guy is determined with a bracket comparison. It turns out that it's more efficient to spend those comparisons to eliminate other possible third place guys. One way to maybe understand this is to redo the problem but with 17 coins, or 32 coins.

By the way, I don't think that it is possible to 'intuitively see this as being optimal' -- I don't really know if there are good ways of proving that solutions to these sorts of problems are optimal, and would be curious to hear from others if there are.