Missing Coin
I recently published the following coin puzzle:
There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.
My readers, David Reynolds and ext_1973756, wrote to me that I am missing a coin of 4 grams. Indeed, the same puzzle with five coins—1, 2, 3, 4, and 5—is a more natural and a better puzzle.
David Reynolds also suggested to go all the way up to 9 coins:
There are nine silver coins marked 1, 2, 3, 4, 5, 6, 7, 8, and 9. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.
It is impossible to resolve this situation with more than nine coins as two weighings provide nine different answers to differentiate coins. But indeed it is possible to solve this problem for nine coins. It is even possible to suggest a non-adaptive algorithm, that is to describe the weighings before knowing the results.
To find such a strategy we need to satisfy two conditions. First, we have to weigh groups of coins of the same supposed weight, otherwise we do not get any useful information. Second, there shouldn’t be any two coins together (in or out of the pan) in both weighings, because it would then be impossible to differentiate between them.
Here is one possible solution of the problem:
- The first weighing: 1, 5, and 9, against 2, 6, and 7
- The second weighing: 1, 6, and 8, against 2, 4, and 9
David Reynolds also suggested a problem in which we do not know whether the fake coin is heavier or lighter:
There are four silver coins marked 1, 2, 3, and 4. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.
Again, four coins is the best we can do when in addition to find it, we also want to determine if it is heavier or lighter. Indeed, if there were five coins we would have needed to cover ten different answers, which is too many for two weighings.
Here is the solution for four coins:
The two weighings are 1+3=4, and 1+2=3. If the first weighing balances, then the fake coin is 2 and the second weighing shows if it is heavier or lighter than it should be. Similarly, if the second weighing balances, then the fake coin is four and we can see whether it is heavier or lighter than it should be. If the left pan is lighter/heavier for both weighings, then the fake coin is 1 and is lighter/heavier. But if one pan is heavier on the first of two weighings and the other pan is heavier on the second weighing, then the fake coin is 3. In both cases it is easy to determine whether the fake coin is heavier or lighter.
Now David is missing a coin. If we just want to find the fake coin without determining whether it is heavier of lighter, we can do it with five coins:
There are five silver coins marked 1, 2, 3, 4, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.
We can use the same solution as the previous (four coins) problem. If the scale balances both times, then the fake coin is 5. However, in this case we will not know whether the coin is heavier or lighter.
We can’t extend this problem to beyond five coins. Suppose we have six coins. We can’t use more than three coins in the first weighing. This is because if the scale unbalances, we can’t resolve more than three coins in one remaining weighing. Suppose the first weighing balances; then we have at least three leftover coins we know nothing about and one of them is fake. These three coins should be separated for the next weighing. That means one of the coins needs to be on the left pan and one on the right pan. We can add real coins any way we need. But if the second weighing unbalances we do not know if the fake coin is on the left and lighter or on the right and heavier.
Share:
David Reynolds:
Very good!
12 July 2013, 2:36 pmTheo:
In the problem with four coins, where you don’t know if the fake coin is heavier or lighter, there is one final possibility. Namely, it is possible that both weighings balance, in which case it turns out I lied to you, and all the coins are real.
12 July 2013, 8:24 pm