Balancing It Out

Time for the solution to the recent balance scale puzzle.

First, notice that there is a symmetry in the problem that needs to be broken, specifically there is no real distinction between "fake" and "genuine", if you swapped those labels the problem is identical. Let us break that symmetry by selecting a single coin and then we are going to show that all the other coins weigh the same as that special one. In effect, I will declare any coin with the same mass as that one to be "genuine" and a coin of any other mass to be "fake".

Now that we have one genuine coin, take the other nine coins and divide them up into three disjoint sets, one of two coins, one of three coins, and one of four coins. We will denote these sets of coins as 1, 2, 3, and 4, so if I say we weigh 3 vs 1+2 I mean to take the set of three coins and weigh them against the set of two coins plus the single genuine coin.

Naturally, our three weighings are going to be some coins against some other coins, equal in number, such that if a weighing is ever imbalanced we are done immediately (we would have proven there is at least one fake and one genuine coin), so we are free to assume that all weighings are balanced (as opposed to other balance scale problems where you have to divide up the tree into "if left heavy", "if right heavy", and "if balanced").

First weighing, 3 vs 1+2. When this is balanced, we know that the number of fakes in 2 (call that x) equals the number of fakes in 3 (so, x is also the number of fakes in 3). Second weighing, 4 vs 1+3. When this is balanced, we know the number of fakes in 4 is also x. Finally, we weigh 1+4 vs 2+3. When this is balanced we know that x=x+x, guaranteeing that x is 0 and there are no fake coins.

It is sort of neat that you can do those weighings in any order you want, since you don't gain information after a weighing (or rather if you did, you were done right away). But if you do the weighings in another order the information is a bit less natural to analyze.