Parallel Weighings
We’ve all been hearing about parallel computing, and now it has turned up in a coin-weighing puzzle invented by Konstantin Knop.
“We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter, but all genuine coins weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts a minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?”
This puzzle reminds me of another coin-weighing problem, where in a similar situation you need to find a fake coin by using one scale with four pans. The answer in this variation would be 55 = 3125. We can divide coins in five groups with the same number of coins and put four groups on the scale. If one of the groups is different (heavier or lighter), then this group contains the fake coin. Otherwise, the leftover group contains the fake coin. This way each weighing reduces the pile with the fake coin by a factor of five. One scale with four pans gives you more information than two scales with two pans used in parallel. We can conclude that Knop’s puzzle should require at least the same number of weighings as the four-pan puzzle for the same number of coins. So we can expect the answer to Knop’s puzzle will not be bigger than 3125. But what will it be?
Share:
Troy:
Divide the coins into three piles, and divide two of the piles into half. One one scale, weight two half piles and weigh the other two half piles on the second scale. If one pair is out of balance, it contains the fake coin. If none of them are, the pile that was not weighed contains the fake coin. Regardless, we have now reduced the total number of coins by 1/3.
At the final step, I think we need to weight a possible fake coin against a known good coin, as weighing the fake coin against a possible fake will only tell us that one of them is a fake, not which one.
Additionally, we can mix in some good coins if needed so that all of the piles divide evenly in half.
Step 5: Weigh two possible fakes against two good coins. Do not weigh one possible fake. (3 coins). Leaves one possible fake coin.
Step 4: Weigh 1 possible fake and 1 good coin vs 2 possible fakes on each scale. Do not weigh 3 coins. (9 coins)
Step 3: Weigh 4 possible fakes and 1 good coin vs 5 possible fakes. Do not weight 9 possible fakes. (27 coins).
Steps 2 and 1 involve using 81 and 243 coins. The maximum number is 3^5 = 243.
31 May 2013, 1:35 pmlvps1000vm:
Divide the coins in six groups, and measure one to another, another to another, with two left out. This way you reduce the space by a factor of 3 each round. In the last round you have three coins and measure two against a neutral coin each. So, at least, 3^5 = 243.
In this solution the information content of each round comes from a space of three possible answers: both scales are even, the first is uneven or the second is uneven. The answer “both scales are uneven” is impossible. Reducing by a factor 3 is optimal if the space of answers has cardinal 3.
Beating 3^5 is only possible if we manage to invent a configuration in which the outcome “both scales are uneven” is possible, otherwise we can’t draw more information. Is it possible?
1 June 2013, 2:55 amJoseph:
Do you just have to find the fake coin, or do you have to find the fake coin AND figure out whether it is heavy or light?
With the classic 12-coin, 3-weighing problem, it makes a difference. If you need to know whether the fake coin is heavy or light, 12 coins is the maximum. If you only need to find the fake, you can handle 13 coins.
1 June 2013, 9:30 amTanya Khovanova:
Joseph,
you just need to find.
1 June 2013, 9:37 amCount Iblis:
Start with dividing by 6, we put 4 groups on the two scales. Then we know if the fake coin is in one of the two piles that were not put on a scale or we find out on which scale it is on. Then we do a measurement to find out if the fake coin is lighter or heavier. If one of the two scales is out of balance, we swap two groups on different scales. There will then be a scale that is off balance. If that’s the same scale that was off balance the first time, then the fake coin is in the pile that wasn’t moved, otherwise it’s on the scale that is now off balance on the pile that was moved there. Since we can see which pile is heavier, we know whether the fake coin is ligher or heavier. If the fake coin is in one of the two piles that wasn’t put on the scales, we replace one pile from each scale by these piles and then we can see which one goes off balance and it will be cear also if the fake coin is ligher or heavier.
Then having determined if the fake coin is ligher of heavier, we can divide the group containing the fake coin in five equal parts, four of them are put on the scales. We can thus reduce the pile containing the fake coin by a factor of 5. So, this method yields N = 6*5^3 = 750.
2 June 2013, 11:07 amlvps1000vm:
@Count Iblis
Good one! You manage to beat the restriction I conjectured because, during the three final rounds, it is meaningful whether a scale falls left, falls right or is balanced, and not just whether it’s balanced or unbalanced. So there are five possible outcomes in these rounds.
2 June 2013, 5:31 pmLily K:
Given the way the problem is worded, N can be infinite.
3 June 2013, 11:35 am“What is the largest number of coins N for which it is possible to find the fake coin in five minutes?”
It is possible to find the fake coin in one weighing no matter how many coins there are just by getting lucky and picking it as one of two.
It should be worded to the effect of “… for which it can be guaranteed to find the fake coin in …”
Tanya Khovanova:
Lily, you are right.
4 June 2013, 10:24 amDavid Reynolds:
Count Iblis showed that by knowing if the counterfeit is lighter or heavier, you can reduce the number of coins to test each
5 June 2013, 3:32 amminute by a factor of five. I will show that this reduction is still possible without knowing if the counterfeit coin is
lighter or heavier as long as only one possibility exists for each coin.
Consider five coins in which you have deduced that, of three, if one is the counterfeit, it must be lighter, and of the other
two, a counterfeit must be heavier. On each scale, you could take one coin from each group and weigh them together against
two known genuine coins, and set aside the fifth. A simpler solution is to weigh two light candidates against each other and
two heavy candidates against each other and set the fifth aside.
In two minutes, you can test 25 coins as long as you have some information on each coin. Put ten on each scale and set five
aside. The ten on each scale must be picked such that, if a scale becomes unbalanced, half of the coins will be proved
genuine.
In three minutes, 50 coins on each scale and set 25 coins aside for 125 coins, etc.
So when information is known before each weighing, the coins that can be tested in n minutes is 5^n.
If no information is known, then in one minute only 3 coins can be tested.
If you have two minutes and no information, put 5 coins on each scale and set 3 aside. 2*5+3=13 coins.
The five coins on a scale refers to five candidate coins. It may be three candidates in one pan and two candidates plus a
genuine coin on the other. Or it could be five candidate coins in one pan an five genuine in the other. If the scale tips,
information will be known about each candidate coin. Use the remaining weighings to reduce the set by five. If neither scale
tipped, the set of coins that was set aside must have the counterfeit and you have one minute less remaining and still no
information.
In three minutes, put 25 coins on each scale and set 13 aside. 2*25+13=63.
In four minutes, 2*125+63=313.
By now, maybe you see the recurrence f(n)=2*5^(n-1)+f(n-1), where f(1)=3, but not quite.
In five minutes, 2*624+313=1561 coins. <– final result.
(Not 2*625+313, since we have no genuine coins to offset an odd number of coins on a scale.)
So we start with 312 coins in each pan and 313 coins set aside. If a scale tips we know that 312 coins are light candidates
and 312 are heavy candidates. That can be reduced to 125, 25, 5, and 1 with the remaining four minutes.
If the scales remain balanced, divide the unknown coins as described and continue.
Tanya Khovanova’s Math Blog » Blog Archive » Parallel Weighings Solution:
[…] recently posted the following coin weighing puzzle invented by Konstantin Knop: We have N indistinguishable coins. One of them is fake and it is not […]
6 August 2013, 7:38 am