Hosted by The Math Forum

Problem of the Week 1065

A Trick with Ten Coins

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

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[log2n] 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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


31 October 2006