Making the Case - Futility Closet

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?

	Select Click for Answer
Divide the coins into nine piles — call them A₁, B₁, C₁, A₂, B₂, C₂, A₃, B₃, and C₃, with sizes 24, 1, 2, 24, 1, 2, 23, 2, 1, respectively. Now use the scale to show that A₁ + B₁, A₂ + B₂, and A₃ + B₃ balance one another, as do B₁ + C₁, B₂ + C₂, and B₃ + C₃. This shows the judge that there are three different ways in which the fake coins might be distributed: one fake coin in each of A₁, A₂, A₃ (sizes 24, 24, 23) one fake coin in each of B₁, B₂, B₃ (sizes 1, 1, 2) one fake coin in each of C₁, C₂, C₃ (sizes 2, 2, 1) Each possibility involves 3 fake coins, not 2, and we’ve managed to convey that fact without revealing the character of any particular coin. (Nicholas Diaco and Tanya Khovanova, “Privacy and Counterfeit Coins,” Mathematical Intelligencer 38:3 [September 2016], 6-10.)

Click for Answer