A Fake Among Eight Coins

There are eight identical-looking coins; one of these coins is counterfeit and is known to be lighter than the genuine coins. What is the minimum number of weighings needed to identify the fake coin with a two-pan balance scale without weights?

Solution

References

A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press, 2011, #10

Solution 1

Select from the given coins two groups of three coins each and put them on the opposite cups of the scale. If they weigh the same, the fake is among the remaining two coins, and weighing these two coins will identify the lighter fake. If the first weighing does not yield a balance, the lighter fake is among the three lighter coins. Take any two of them and put them on the opposite cups of the scale. If they weigh the same, it is the third coin in the lighter group that is fake; if they do not weigh the same, the lighter one is the fake.

Thus the problem is solvable in two weighings. It's not quite clear why the problem has been set up for 8 and not 9 coins. The above solution shows that 1 weighing is sufficient to detect a lighter fake among 3 coins. Splitting 9 coins into three groups and thinking of each as a "big coin", reduces the problem to the previous one: it takes just one weighing to detect the lighter group. An additional weighing finds the fake coin among the three in the lighter group.

Solution 2

The problem has an alternative solution in which the second weighing does not depend on the results of the first one.

Label the coins by the letters A, B, C, D, E, F, G, H. On the first weighing, weigh A, B, C against F, G, H. On the second weighing, weigh A, D, F against C, E, H. If ABC = FGH (the first weighing results in a balance), all these six coins are genuine, and therefore the second weighing is equivalent to weighing D against E. If ABC < FGH, only A, B, and C may still be fake. Therefore if on the second weighing ADF = CEH, B is the fake; if ADF < CEH, A is the fake; and if ADF > CEH, C is the fake. The case of ABC > FGH is symmetric to the case just discussed.

Weighing Coins, Balls, What Not ...

71546796