You have 12 gold coins — or so you think! One is fake and is known to have a different weight than the others. It could be heavier or lighter; you only know it’s wrong. Using the same simple balance scale, how do you determine the incorrect coin, and whether it is heavier or lighter, in only three weighings?
The criteria for the unique coin’s identity to be known is
- It must be weighed at least once
- If put on the scale with an equal number of coins on each side it cannot be evenly balanced
- If put on the scale more than once with an even number of coins on each side it must weight consistently more or consistently less than the other side
This is the framework for finding the solution — just find a weighing scheme that lets you remove 11 of the coins from this criteria with one that satisfies it. There is some branching allowed, depending on the result of the previous weighing you can alter which coins you put on each side of the scale. I call these Scale Configs and there are two per branch:
For example, putting coins 0,1,2,3 on one side of the scale and 4,5,6,7 on the other is Scale Config 1
My configurations are as follows:
For example, if coin 8 is made of a heavier material than metal our path would go:
- Weigh [0,1,2,3] against [4,5,6,7]. They are evenly balanced (go to Config 3)
- Weigh [5,6,7] (known non-unique coins) against [8,9,10]. [8,9,10] is heavier meaning the coin is among those three and heavier
- Weigh  against . 8 is heavier and therefore the unique coin
Making this in Python helped me understand the problem and the decisions I actually got to make. I was fairly confident in my Configurations 1,3,6,7 because I could logic though them — but 2, 4 and 5 were all dependent on one another and therefore annoying. It ended up saving time just writing a way to brute force different configurations for those three — yielding the solution above.
The code creates configurations for both sides of C2, C4, C5 then tests every coin as being both heavier and lighter. If it can deduce each one then it is a pass. It took about 20,000 iterations to get to the working solution, above.