You are presented with a set of 90 coins, appearing identical.
Actually, 89 of them are identical, but one has a different weight.
Using balance scales you have to find the odd coin,
paying $10 each time you use the scales.
What is the maximal (i.e. the worst case) cost to accomplish it?
I assume that the problem asks for a methodology that minimizes the maximum cost.
There are two key insights, I think:
a) If we do not know whether the odd coin is lighter or heavier, we can eliminate half (or almost half) the coins by weighing 1/4 of the coins against a different 1/4 of the coins. If they equal, then they are good. If not, then the other half are good. However, if we know whether the odd coin is heavier, then we can eliminate 2/3 of the coins on each weighing by weighing 1/3 against 1/3. If the number of coins is large enough, it pays to figure out early whether the odd one is heavier or lighter, even if it does not necessarily eliminate as many as possible.
b) We can potentially figure out whether it is heavier or lighter in two weighings, by first weighing 1/3 of the coins against another 1/3. But there is an even better approach, considering the problem objective and the initial number of coins (90).
The following method looks good to me.
1) Weigh 27 coins against 27. If they are unequal, then weigh the lighter set against a different 27. After these two weighings, we know which set of 27 contains the odd coin, and whether is it heavier or lighter. A 3rd weighing of 9 vs. 9 gets us down to 9 coins, one of which is odd. Then weigh 3 vs. 3 to get down to 3, and 1 vs 1 to isolate the odd coin. 5 weighings.
2) If, in case 1, the first weighing is equal, then weigh either set against a different 27. If they are unequal, then we once again know which set of 27 contains the odd coin, and whether is it heavier or lighter. Proceed as in case 1. 5 weighings
3) If, in case 2, the first two weighings are equal, then we are down to 9 coins after two weighings. Divide the 9 into three piles of 3, and use two weighings to determine which one has the odd coin and whether it is lighter or heavier. Use the final weighing to isolate the odd coin. 5 weighings.
So, this method always uses 5 weighings, no more and no less. I have not proven that it is optimal, but it is hard to believe that there is a method where 4 weighings is the worst case, give that 3^4 is only 81. There might be a method that occasionally achieves 4 weighings.
Nice problem, Ady. I wait with anticipation to see if a better solution emerges.
Where there's a will, there's a weigh (spoiler?)
