Six Coins, One Honest Scale

Worked solution

The answer is 4. Write $x_i = 1$ if coin $i$ is counterfeit and $0$ otherwise. Weighing a set reports exactly how many counterfeits it contains, i.e. the sum of its $x_i$. **A four-weighing strategy.** First weigh coins 1 and 2 together, learning $x_1 + x_2$. *If $x_1 + x_2$ is 0 or 2,* both coins are known and four coins remain for three weighings. Weigh {3, 4}. If it reads 0 or 2, coins 3 and 4 are known; weigh 5 alone, then 6 alone. If it reads 1, weigh {3, 5}: a reading of 0 means $x_3 = x_5 = 0$, $x_4 = 1$, and a reading of 2 means $x_3 = x_5 = 1$, $x_4 = 0$ (then weigh 6 alone); a reading of 1 means $x_4 = x_5 = 1 - x_3$, and weighing {4, 5, 6} gives $2(1 - x_3) + x_6$, whose four possible values 0, 1, 2, 3 identify both $x_3$ and $x_6$. *If $x_1 + x_2 = 1$,* then $x_2 = 1 - x_1$. Weigh {1, 3, 4}. A reading of 0 or 3 fixes $x_1, x_3, x_4$ (and so $x_2$), and two single weighings finish coins 5 and 6. Suppose the reading is 1 (the reading 2 is the mirror image, obtained by swapping the roles of genuine and counterfeit everywhere). Then $(x_1, x_2, x_3, x_4)$ is one of $A = (1,0,0,0)$, $B = (0,1,1,0)$, $C = (0,1,0,1)$, with $x_5, x_6$ free. Weigh {2, 3, 5}: it shows $x_5$ under $A$, $2 + x_5$ under $B$ and $1 + x_5$ under $C$. A reading of 0 or 3 identifies everything but coin 6, which a single weighing settles. A reading of 1 leaves $A$ with $x_5 = 1$ or $C$ with $x_5 = 0$; weigh {2, 4, 6}, which shows $x_6$ under $A$ and $2 + x_6$ under $C$. A reading of 2 leaves $B$ with $x_5 = 0$ or $C$ with $x_5 = 1$; weigh {4, 5, 6}, which shows $x_6$ under $B$ and $2 + x_6$ under $C$. Either way the fourth reading distinguishes all remaining cases. **Three weighings are not enough.** Simple counting does not settle this (three weighings of six coins could in principle produce many more than 64 reading sequences), but an exhaustive computer search over every adaptive three-weighing strategy, each state being the set of patterns still consistent with the readings, finds that none separates all 64 patterns. Hence the minimum is 4.