Brainteasers · Weighing and search · Hard
Heavier or lighter
A batch of coins look identical. All but one weigh exactly the same; the odd coin is either slightly heavier or slightly lighter than the rest, and you do not know which. You have a balance with two pans and no weights, and no other coins: a weighing puts any coins from the batch on each pan and tells you only which pan is heavier, or that the two balance. You are allowed three weighings, and at the end you must name the odd coin and say whether it is heavier or lighter. What is the largest number of coins in the batch for which you can be certain to succeed, however the weighings turn out?
Answer and solution
Answer
12
Solution
Each outcome of the first weighing must leave at most 9 cases for the last two weighings, which 13 coins cannot arrange and 12 can.
With 13 coins there are 26 cases. A first weighing of k against k leaves 2k cases if it tips one way and 2(13 − 2k) if it balances; both must be at most 9, so k ≤ 4 and 13 − 2k ≤ 4, which is impossible. With 12 coins, weigh 4 against 4: each outcome leaves 8 cases. If it balances, weigh three of the four unweighed coins against three known genuine ones; if it tips, move coins between pans and off the balance so that each of the three outcomes leaves at most three cases, and one more weighing separates them. The answer is 12.