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?
Five weighings can actually find the odd coin if there are 94 identical coins and 1 odd one (95 total). I reached this method with a little help from Wikipedia (see entry for "Balance Puzzle")
a) Use two weighings to weigh 27 vs 27 vs 27. If they are unequal, then we we know whether the odd coin is lighter or heavier, and in which set of 27 it is. 3 more weighings isolate it.
b) If the first two weighings all balance, then the odd coin is one of 14 coins. Number them 1 through 14, and take one of the normal coins and number it 0. Take three weighings as follows:
0, 1, 4, 5, 6 against 7, 10, 11, 12, 13
0, 2, 4, 10, 11 against 5, 8, 9, 12, 13
0, 3, 8, 10, 12 against 6, 7, 9, 11, 13
If the scales all balance, then the odd coin is #14, but we do not know whether it is heavier or lighter. Otherwise, it is possible to deduce which coin is counterfeit and whether it is lighter or heavier (which is 26 different possibilities).
Using 5 weighings, is 95 the most coins that can be handled with 5 weighings?
Well, the information theory limit is 3^5 = 243 states that can be distinguished with 5 weighings each of which has three possible outcomes (balanced, left heavier and right heavier).
In theory, then, we can distinguish between 1 coin (weight unknown) and 121 which can be heavier or lighter. Since 121 is not divisible by 3, however, this would take one coin that is known to be good. Since we do not have that, I suspect that the most we can handle is closer to 120 which can be heavier or lighter, using 5 weighings of 40 vs. 40 where we use some scheme similar to step (b) above. 120 + 1 (weight unknown) = 121, so I guess the limit is 121, but I have not fully developed the method, so this is just a guess.
Edited on December 18, 2013, 10:37 pm