You have N coins, one of which is counterfeit. All real coins have the same weig

Question

You have N coins, one of which is counterfeit. All real coins have the same weight. The counterfeit coin is either heavier or lighter, but you don't know which in advance. You have a balance, with which you can compare two sets of coins A and B, to determine whether A is heavier, B is heavier, or they weigh the same. You also have an unlimited supply of known real coins. The problem is to determine which coin is counterfeit, and whether it is heavy or light. Show that if N = 13, it is possible to locate and determine the weight of the counterfeit coin in 3 weighings, and that if N = 14, at least 4 weighings are required.

Explanation / Answer

This one's a (great) classic. It has been presented in many different ways. At one point, it was known as the Counterfeit Coin Problem: Find a single counterfeit coin among 12 coins, knowing only that the counterfeit coin has a weight which differs from that of a good coin. You are only allowed 3 weighings on a two-pan balance and must also determine if the counterfeit coin is heavy or light. Expanding on the question a little, we'll show that 3 weighings are enough to... Find an odd marble among 12 and tell if it's heavy or light. Find an odd marble among 13. If you are given an extra regular marble, you may also... Find an odd marble among 13 and tell if it's heavy or light. Find an odd marble among 14. (Please, understand that the extra "reference" marble is in addition to the 13 or 14 "unknown" ones, but its presence makes the problem simpler to solve.) We'll also prove, in each case, that the above is the best that can be achieved. First, let's deal with 12 marbles, call them ABCDEFGHIJKL: First weighing: Compare ABCD and EFGH. If ABCD=EFGH, you know the special marble is among IJKL. Use your 2nd weighing to compare AI and JK (you know A is ordinary): If AI=JK, you know L is the odd marble. You may compare L and A in the 3rd weighing to determine if L is heavy or light. If AI and JK are not equal, you know L is ordinary. Use your 3rd weighing to compare J and K. If J=K, you know I is the special marble (the result of the second weighing tells you if it's heavy or light). Otherwise, the special one is either J or K and you can tell which: It's the heavier one if we had AICFL : Either F is light or one of AB is heavy. Compare A and B in the 3rd weighing to find out. ABCD>EFGH and ABE

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.