math problem

[kai]

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

[ZeeJustin]

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>

[ZeeJustin]

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.

[ZeeJustin]

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.

[Sholar]

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

[TomCowley]

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?

[TomCowley]

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.

[Sholar]

Nice.

[skates]

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.

[Sholar]

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.