How many coins in three weighings
Among a set of coins, exactly one is fake. It is either heavier or lighter than the genuine coins, and you do not know which. You have a two-pan balance and no other coins. A weighing tells you whether the left pan is heavier, the right pan is heavier, or the pans balance.
What is the largest number of coins for which three weighings are always enough to find the fake coin and tell whether it is heavier or lighter?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Count. Three weighings have possible outcomes. With coins, how many situations must they tell apart?
The counting bound allows 13. Look at the first weighing with 13 coins: what happens when it balances, and what happens when it does not?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Counting outcomes gives at most 13 coins. Looking at the first weighing rules out 13. An explicit scheme handles 12.
Upper bound. With coins there are situations (which coin, heavier or lighter), and three weighings have outcomes, so and .
13 is impossible. Put coins on each pan in the first weighing.
- If it tips, the fake is one of the coins on the scale, heavy on the low side or light on the high side: situations, which two weighings (9 outcomes) can only separate if .
- If it balances, the fake is among the coins left off, with situations, which needs , so .
Both cannot hold.
12 is possible. Number the coins 1 to 12.
Weighing 1: 1, 2, 3, 4 against 5, 6, 7, 8.
If it balances, the fake is among 9 to 12, and coins 1 to 8 are genuine. Weigh 9, 10, 11 against 1, 2, 3.
- Balance: coin 12 is fake; weigh it against coin 1 to see whether it is heavy or light.
- 9, 10, 11 heavier: the fake is one of them and heavy. Weigh 9 against 10: the heavier one is fake, or 11 if they balance.
- 9, 10, 11 lighter: the same, with “lighter”.
If 1 to 4 are heavier (the other case is symmetric), either one of 1 to 4 is heavy or one of 5 to 8 is light, and 9 to 12 are genuine. Weigh 1, 2, 5 against 3, 4, 6.
- Balance: the fake is 7 or 8, and light. Weigh 7 against 8: the lighter one.
- Left heavier: 1 or 2 is heavy, or 6 is light. Weigh 1 against 2: the heavier one is fake; if they balance, 6 is light.
- Right heavier: 3 or 4 is heavy, or 5 is light. Weigh 3 against 4: the heavier one is fake; if they balance, 5 is light.
Every case ends with the fake coin and its direction, so the answer is 12.
With a spare genuine coin the bound of 13 can be reached: the spare lets the first weighing put 5 unknown coins against 4 unknown plus the spare. In general, weighings handle coins without a spare and with one.