Problem of the Week 1065

A Trick with Ten Coins

Alice: I have ten coins here. They are identical except that some of them may be made of a different alloy, in which case there will be exactly two different weights. I don't need to know which are which, but I do want to know if they all weigh the same. Can I borrow your balance to find out?

Bob: Sure, but it's just an equal-arm balance.

Alice: No problem: I can weigh #1 against #2. If they balance, I'll weigh 1 and 2 against 3 and 4. If they also balance, I can weigh 1, 2, 3 and 4 against 5, 6, 7, and 8. Then if they balance, I can weigh 9 and 10 against any two of them and I'm done.

Bob: I'm sorry, but I'm in a hurry to lock up the lab for the weekend and I can only let you use the balance three times.

Show how Alice can determine whether the coins all weigh the same in just three balancings.

Background. For the general problem with n coins there is an obvious solution using, in the general case, Ceiling[log₂n] weighings: Test 1 against 2; if they balance, test 1 and 2 against 3 and 4; if they balance, test 1, 2, 3, and 4 against 5, 6, 7, and 8, and so on. It was conjectured that this formula was the best possible, and so came as quite a surprise when, in 1997, it was discovered by Kozlov and Vu that the 10-coin problem can be solved in three, as opposed to the conjectured four, weighings. The solution to the given problem is not complicated, but might be hard to find.

Thanks to Robert Dawson (St. Mary's University, Halifax, Nova Scotia) for valuable consultations.

© Copyright 2006 Stan Wagon. Reproduced with permission.