Making the Case

Alexander Shapovalov suggested an unusual coin-weighing problem for the sixth international Kolmogorov math tournament in 2007:

A judge is presented with 80 coins that all look the same, knowing that there are either two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

A lawyer knows that there are exactly three fake coins and which ones they are. The lawyer must use a balance scale to convince the judge that there are exactly three fake coins and that it is impossible for there to be only two fake coins. She is bound by her contract not to reveal any information about any particular coin. How should she proceed?

The lawyer might try dividing the 80 coins into three groups of 26, each group containing one fake coin, with two coins left over. With two weighings she could then show that the three groups have the same weight. From this the judge could conclude that either (a) there are 3 fake coins, one in each group, or (b) there are 2 fake coins, both in the leftover group. The lawyer could then weigh one of the leftover coins against a real coin taken from one of the three groups, to show that these balance. This would prove to the judge that there are 3 fake coins (because if there were only 2 then possibility (b) above would be ruled out). However, this strategy is “indiscreet” — it would reveal to the judge the true character of each of the leftover coins, which the lawyer has pledged not to do. How should she proceed instead?

Click for Answer