Solution
Three Light Fakes
Show the problem again
Eight coins look identical. Exactly three are counterfeit; all counterfeits weigh the same as each other and are lighter than every genuine coin, and all genuine coins weigh the same. You have a two-pan balance scale with no weights, and each weighing must put the same number of coins on each pan. What is the minimum number of weighings that always suffices to determine which three coins are counterfeit?
Worked solution
The answer is 4. **Three weighings are not enough.** There are $\binom{8}{3} = 56$ possible sets of counterfeits, but three weighings have only $3^3 = 27$ outcome sequences, so two different sets would always produce the same readings. **Four weighings suffice.** Number the coins 1 to 8. A pan is lighter exactly when it holds more counterfeits. *Weighing 1: {1, 2} against {3, 4}.* **If it balances,** both pairs hold the same number of fakes, which is 0 or 1 (two each would be four fakes). Weigh 1 against 2. - If 1 is lighter (the case 2 lighter is symmetric), coin 1 is fake, coin 2 genuine, exactly one of 3, 4 is fake, and exactly one of 5 to 8 is fake. Weigh {3, 5} against {4, 6}. If the left is lighter, the fakes are {3, 5}, {3, 7} or {3, 8}: weigh 5 against 7 (lighter one, or 8 if balanced). If the right is lighter, symmetrically weigh 6 against 7. If it balances, the fakes are {3, 6} or {4, 5}: weigh 3 against 4. - If 1 and 2 balance, they are both genuine (they cannot both be fake), so 3 and 4 are genuine and three of 5 to 8 are fake: exactly one of those four is genuine. Weigh 5 against 6: the heavier one is the genuine coin, and if they balance both are fake and weighing 7 against 8 finds the genuine one. **If it tips,** say {3, 4} is lighter (the other case is symmetric). Weigh 3 against 4. - If 3 is lighter (or symmetrically 4), coin 3 is fake and 4 genuine, so {3, 4} holds one fake and {1, 2} must hold none: the other two fakes are among 5 to 8. Weigh 5 against genuine coin 1. If 5 is lighter, it is fake and one of 6, 7, 8 is the last fake: weigh 6 against 7. If they balance, two of 6, 7, 8 are fake: weigh 6 against 7, and the fakes are the lighter one with 8, or 6 and 7 if they balance. - If 3 and 4 balance, both are fake (both genuine would contradict the first weighing), and the third fake is one of 1, 2, 5, 6, 7, 8. Weigh {1, 5} against {2, 6}; the lighter pair is then split by one more weighing, and a balance means the fake is 7 or 8, separated by weighing 7 against 8. Every branch ends after at most four weighings, so the minimum is 4. (An exhaustive computer search over all adaptive strategies agrees.)
Source: Multiple-counterfeit variant of the balance-scale puzzle family; original design for AxiomIQ, no traceable source.