Heavier or Lighter
In my old essay I presented the following coin problem.
We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weigh the same. The fake coin is either lighter or heavier than a real coin. We also have a balance scale. Unlike in classical math problems where you need to find the fake coin, in this problem your task is to figure out whether the fake coin is heavier or lighter than a real coin. Your challenge is that you are only permitted to use the scale twice. Find all numbers N for which this can be done.
Here is my solution to this problem. Let us start with small values of N. For one coin you can’t do anything. For two coins there isn’t much you can do either. I will leave it to the readers to solve this for three coins, while I move on to four coins.
Let us compare two coins against the other two. The weighing has to unbalance. Then put aside the two coins from the right pan and compare one coin from the left pan with the other coin from the left pan. If they balance, then the right pan in the first weighing contained the fake coin. If they are unbalanced then the left pan in the first weighing contained the fake coin. Knowing where the fake coin was in the first weighing gives us the answer.
It is often very useful to go through the easy cases. For this problem we can scale the solution for three and four coins to get a solution for any number of coins that is divisible by three and four by just grouping coins accordingly. Thus we have solutions for 3k and 4k coins.
For any number of coins we can try to merge the solutions above. Divide all coins into three piles of size a, a and b, where a ≤ b ≤ 2a. In the first weighing compare the first two piles. If they balance, then the fake coin must be among the b remaining coins. Now pick any b coins from both pans in the first weighing and compare them to the remaining b coins. If the first weighing is unbalanced, then the remaining coins have to be real. For the second weighing we can pick a coins from the remaining pile and compare them to one of the pans in the first weighing.
The solution I just described doesn’t cover the case of N = 5. I leave it to my readers to explain why and to solve the problem for N = 5.
Share:
mashplum:
For 3 coins, compare any 2. If they match, they are real, and you just compare one of them to the fake. If they don’t match, compare the 3rd coin to the lighter of the first 2. If they match, they are real and the fake is heavy. If they don’t match, the fake is light.
For 5 coins, put 2 on each side of the balance. If they match, they are real, and you just compare one of them to the fake. If they don’t match, compare the 2 coins from the lighter side. If they match, they are real and the fake is heavy. If they don’t match, the fake is light.
You can use a ≤ b ≤ 2a for N=5 since the piles are impossible to arrange. If a=1, then b=3, and b>2a. If a=2, then b=1, and a>b.
12 April 2011, 6:58 pm