A Faulty Scale
Today I have two new coin puzzles that were inspired by my son, Alexey Radul:
You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have a balance scale which might or might not be faulty. A faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of weighings you need in order to figure out whether the scale is faulty?
If you think about it, this problem is isomorphic to a known problem I wrote about before:
You have N ≥ 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is either lighter than the real ones or heavier than the real ones. You also have a normal balance scale. What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?
To make things more interesting let’s mix the problems up.
Share:You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have M > 1 identical-looking balance scales. All but one of them are normal and one is faulty. The faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of total weighings needed to figure out which scale is faulty?
Zet:
If N is even and M>3 it seems easy: just divide the coins in 2 equal parts and test all but one of the scales. The scale which gives a different result is the faulty one. If no scale differs, the untested one is faulty.
If M=3 or N is odd you need 1 extra weighing (in the first case because you don’t know which half of the coins contains the fake one, in the second case because in the worst case your first weighing results in equal weight, and then you still need at least M-1 weighings for M scales.
For M=2 it’s a little bit trickier and depends on the exact number of coins.
17 November 2016, 10:55 amOlga:
For the problem 1 – one weighing: place one coin on one pan and two coins on the other.
20 November 2016, 6:22 pmJeroen:
Expanding on Olga’s brilliant solution:
For problem 3: if M = 2^x -1, a single weighing is enough (given enough coins, N >= M).
M=3: Place scale 2 (plus 1 coin) and scale 3 on different sides of scale 1. Place 1 coin on 1 side of scale 2, and 1 coin on one side of scale 3.
M=7: As above; but place scale 4 (plus 1 coin) and 5 on opposing sides of scale 2, and scale 6 (plus 1 coin) and 7 on opposing sides of scale 3.
etc.
23 November 2016, 10:52 amtanyakh:
Olga,
Brilliant.
26 November 2016, 11:12 amMustafa:
To the problem you mentioned was isomorphic to the initial problem, you say:
“You have N ≥ 2 identical-looking coins”
If N = 2, one will be light and one heavy, but you won’t know which is fake.
So isn’t the statement as follows “What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?” a loaded question?
Although if you think about it, if they are identical in looks and must be placed on a balance scale like, then they probably look and feel the same, and if they feel the same, they are probably made out of the same material, in which case, the heavier coin would be worth more, in terms of material. A skilled metal worker would be able to extract the excess metal out of the coin, and leave the remaining coin looking untouched, in which case, you now have a coin AND a small chunk of metal alloy, however, if you don’t do the metal work, or if it’s not done for free, it’s probably gonna cost more than any of today’s legal tender in coins, or two of them for that matter. Unless it is an antique coin, in which case, if the fake one is a modern replica, I wouldn’t care much for it, however if it’s an ancient duplicate of the coin from its time, that would be pretty cool.
Long story short, N > 2.
28 November 2016, 3:33 pmAlucard:
I think in any case we need M-1 weighings. Just put 1 coin on a pan and the other one empty. Even the fake coin must have weight, so we can definitely know if the scale is fake or not.
30 November 2016, 5:29 am