Ten Coins
Among ten given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale?
When I first received this puzzle from Ken Fan I thought that he mistyped the number of coins. The solution for eight coins was so easy and natural that I thought that it should be eight — not ten. It appears that I was not the only one who thought so. I heard about a published paper with the conjecture that the best you can do is to prove uniformity for 2n coins in n weighings.
I will leave it to the readers to find a solution for eight coins, as well as for any number of coins less than eight. I’ll use my time here to explain the solution for ten coins that my son Sergei Bernstein suggested.
First, in every weighing we need to put the same number of coins in both pans. If the pans are unbalanced, the coins are not uniform; that is, some of them are real and some of them are fake. For this discussion, I will assume that all the weighings are balanced. Let’s number all coins from one to ten.
Consider two sets. The first set contains only the first coin and the second set contains the second and the third coins. Suppose the number of fake coins in the first set is a and a could be zero or one. The number of fake coins in the second set is b where b is zero, one or two. In the first weighing compare the first three coins against coins numbered 4, 5, and 6. As they balance the set of coins 4, 5, and 6 has to have exactly a + b fake coins.
In the second weighing compare the remaining four coins 7, 8, 9, and 10 against coins 1, 4, 5, and 6. As the scale balances we have to conclude that the number of fake coins among the coins 7, 8, 9, and 10 is 2a + b.
For the last weighing we compare coins 1, 7, 8, 9, and 10 against 2, 3, 4, 5, and 6. The balance brings us to the equation 3a + b = a + 2b, which means that 2a = b. This in turn means that either a = b = 0 and all the coins are real, or that a = 1, and b = 2 and all the coins are fake.
Now that you’ve solved the problem for eight and less coins and that I’ve just described a solution for ten coins, can we solve this problem for nine coins? Here is my solution for nine coins. This solution includes ideas of how to use a solution you already know to build a solution for a smaller number of coins.
Take the solution for ten coins and find two coins that are never on the same pan. For example coins 2 and 10. Now everywhere where we need 10, use 2. If we need both of them on different pans, then do not use them at all. The solution becomes:
The first weighing is the same as before with the same conclusion. The set containing the coin 1 has a fake coins, the set containing the coins 2 and 3 has b fake coins and the set containing coins 4, 5, and 6 has to have exactly a + b fake coins.
In the second weighing compare the four coins 7, 8, 9, and 2 against 1, 4, 5, and 6. As the scale balances we have to conclude that the number of fake coins among 7, 8, 9, and 2 is 2a + b.
For the last weighing we compare coins 1, 7, 8, and 9 against 3, 4, 5, and 6. If we virtually add the coin number 2 to both pans, the balance brings us to the equation 3a + b = a + 2b, which means that 2a = b. Which in turn means, similar to above, that either all the coins are real or all of them are fake.
It is known (see Kozlov and Vu, Coins and Cones) that you can solve the same problem for 30 coins in four weighings. I’ve never seen an elementary solution. Can you provide one?
Share:
saar:
hi
14 November 2010, 4:10 amwell’ i just want to thank u, and your son, for this post (and all the others).
Witold:
Using the method from the paper by Kozlov and Vu “Coins and Cones”, we get the following solution.
1. Divide the 30 coins into 5 groups A4, A5, A6, A7, A8 of 4, 5, 6, 7, 8 coins, respectively.
2. Make the following weighings.
a) A4+A5+A6 vs. A7+A8.
b) A4+A7 vs. A5+A6.
c) A6+A7 vs A5+A8.
d) A4+A8 vs. A5+A7.
3. Assume now the scale balances in all the cases (otherwise, we’ve shown that the set isn’t uniform). Mimicking your approach, let a4, a5, a6, a7, a8 be the number of heavier coins in A4, A5, A6, A7, A8, respectively. Our goal is to prove that they are all zero or that each aj is j, for j=4,5,6,7,8.
4. Let a4 be arbitrary.
– Adding a) and b), we get a8=2*a4.
– Adding a) and c), we get a6=(2*a8-a4)/2=3*a4/2.
– Adding a) and d), we get a7=(2*a4+a6)/2=7*a4/4.
– From a), we get a5=a7+a8-a4-a6=5*a4/4.
5. This means that a4 must me divisible by 4, so the only allowed values are 0 and 4. To complete the proof, observe that the formulas from 4. imply the following.
25 November 2010, 4:06 ama) If a4=0, then aj=0, j=4,5,6,7,8.
b) If a4=4, then aj=j, j=4,5,6,7,8.
Tanya Khovanova:
I received an email from Konstantin Knop with a solution with four weighings and 30 coins based on equalities (we have groups of 2, 5, 6, 8, and 9 coins):
2 + 6 = 8
2 + 9 = 5 + 6
6 + 8 = 5 + 9
2 + 5 + 8 = 6 + 9
For 5 weighings and 114 coins the groups are: 9, 12, 20, 22, 25 and 26. For 6 weighings and 454 coins the groups are: 24, 35, 42, 62, 76, 85 and 130.
18 December 2010, 6:17 pmTom Verhoeff:
You mentioned 8 and fewer coins explicitly (as “easy”). Does the method for 10 coins also work (after adaptation) for 9 coins? It is not obvious that the problem is “monotonic”.
28 February 2021, 4:33 pmTom Verhoeff:
To answer my earlier question: yes, the method for ten coins can be made to work for nine as well, by introducing a phantom coin that is matched with a real coin, in such way that the phantom coin and its real counterpart are always on opposite sides of the balance (that way, both can be left out). But it is not clear whether this can be made to work in general.
1 March 2021, 1:33 pm