Dear Uncle Colin,
I have twelve coins, one of which is counterfeit. I don’t know if it’s heavier or lighter than the others, but I’m allowed three goes on a balance scale to determine which coin it is and whether it’s light or heavy. Can you help?
Some Coins Are Light, Evidently
Hi, SCALE, and thanks for your message!
This is a classical puzzle, but one I can never remember the answer to and have to work out fresh each time. So I’m especially grateful: this time, I got a Flash of Insight that made it possible to solve.
(If you want to solve it yourself, now would be an excellent time to do so: below the line are spoilers.)
The Flash of Inspiration was that:
- There are 24 possible solutions to the problem (any one of the 12 coins could be heavy, or any one of them could be light)
- If each weighing reduces the number of possibilites to about a third of what they were before, we’ll have a solution!
In particular, the first weighing needs to reduce the solution space from 24 elements to eight.
Pick eight of the coins and weigh them four against four. There are two possibilities.
If one of the pans drops, then we have four coins that are potentially heavy, four that are potentially light, and the remaining four we know are genuine. This is situation A; our solution space now has eight elements.
If the pan stays level, then one of the remaining four coins is fake, and we don’t know whether it’s light or heavy. This is situation B, which also has eight elements.
Weighing 2, situation A
This is the one that took me the longest to figure out: with eight possible solutions, I need a weighing that eliminates three (or two) possibilities, no matter what happens.
My first thought was to weigh three of the potentially heavy coins and three of the potentially light coins against six genuine coins - but unfortunately, I only have four genuine coins, so I can’t do that.
Instead, the trick is to put two possibly-heavy coins and a possibly-light coin in each pan.
If one of the pans drops, then either one of the two heavy coins on that side or the light coin on the other is the counterfeit one - there are now three possibilities. (This is situation A1).
If they balance, then we know our counterfeit must be one of the ones we didn’t just weigh - one of which we suspect is heavy, one of which we suspect is light - this is situation A2.
Weighing 2, situation B
If we weigh three of the suspect coins against three of the genuine coins (this time, we have plenty of those), either the suspect coins will drop (in which case one of them is heavy - B1), rise (in which case one of them is light - B2) or not move (in which case the remaining suspect coin is counterfeit - B3).
Now we’ve got six possible situations to handle for the final weighing.
- A1: We have two possibly-heavy coins against one possibly-light coin. Weigh the two possibly-heavy coins; if one drops, we know it’s heavy; if neither does, the other must be light.
A2: We have a possibly-heavy coin and a possibly-light coin. Weight the two against two genuine coins. If the suspect coins drop, the possibly-heavy one is definitely heavy; similarly for the light one if it rises.
B1: We have three possibly-heavy coins. Weigh two against each other: if one pan drops, it contains the heavy coin; if neither does, then the other is heavy.
B2: We have three possibly-light coins. Do the same as for B1, with the obvious substitutions.
- B3: We have a counterfeit coin, but don’t know whether it’s heavy or light. Weight it against a genuine coin.
And there you have it! We’ve identified the bad coin and how it’s bad.
Hope that helps!
- Uncle Colin
A selection of other posts
subscribe via RSS