Gold, Silver, and Bronze Coins
Here’s a neat coin puzzle I received by email from my reader s_hskz2 (at twitter.com).
Puzzle. You have 9 coins: 3 gold coins, 3 silver coins, and 3 bronze coins. Within each metal, the coins are indistinguishable. Exactly one gold, one silver, and one bronze coin are counterfeit; the other six are genuine. You are provided with a magic bag that functions as follows: when you place a subset of coins into the bag and cast a spell, the bag glows if and only if the subset contains all three counterfeit coins. Can you identify all three counterfeit coins using at most 5 tests?
I tried to find an easy solution and didn’t. Then I decided to use information theory to guide me to an answer. Unsurprisingly, it worked. The solution wasn’t trivial, but it was a lovely practice in using information theory for such puzzles.
Later, s_hskz2 sent me a more difficult version: There are 10 coins of each kind, and you are allowed to test 10 times, but I was too lazy to try.
Share:
Sanandan Swaminathan:
This is an interesting problem. 5 tests can give us 32 different outcomes, and we have 27 possible triads of bad coins. Success in the first test should cover at least 27 – 16 = 11 triads, otherwise there would be too many triads to cover in the remaining 4 tests if test1 fails (bag does not glow). For test1, let us look at the possibilities for the number of gold, silver, bronze coins we should put in the bag.
3, 3, 3 or 0, 0, 0: This will give us no information. Reject.
3, 3, 2: If test1 succeeds, we will have 18 triads to cover in 4 tests. Reject.
3, 3, 1: If test1 fails, we will have 18 triads to cover in 4 tests. Reject.
3, 2, 2: If test1 succeeds, the 12 triads can be resolved in 4 tests. If test1 fails, the 15 triads can be covered in 4 tests. KEEP.
3, 2, 1 or 3, 1, 1 or 2, 2, 2 or 2, 2, 1 or 2, 1, 1 or 1, 1, 1: In all these cases, If test1 fails, we will have too many triads to cover in 4 tests. Reject.
So, we should put 3, 2, 2 of the coins in the bag for test1. Let the coins be G1, G2, G3, S1, S2, S3, B1, B2, B3.
Test1: Put G1, G2, S1, S2, B1, B2, B3 in the bag (based on 3, 2, 2 aka 2, 2, 3). If test1 succeeds (bag glows), we can see that it’s easy to determine the 3 bad coins.
Test2: Put G1, S1, S2, B1, B2, B3. If success, G1 is bad, otherwise G2. Suppose G1 turns out bad.
Test3: Put G1, S1, B1, B2, B3. If success, S1 is bad, otherwise S2. Suppose S1 turns out bad.
Test4: Put G1, S1, B1, B2. If failure, B3 is bad, and we are done. Otherwise, B1 or B2 is bad. Suppose it turns out that B1 or B2 is bad.
Test5: Put G1, S1, B1. If success, B1 is bad, and we are done. Otherwise, B2 is bad, and we are done.
On the other hand, if test1 fails (bag doesn’t glow), we have a more interesting situation. We are left with 4 tests that can resolve 16 triads. And we have the following 15 possible triads remaining (getting pretty tight):
G3, S3, (B1 or B2 or B3)
G3, S2, (B1 or B2 or B3)
G3, S1, (B1 or B2 or B3)
G1, S3, (B1 or B2 or B3)
G2, S3, (B1 or B2 or B3).
For test2, we can’t just put something like G3, all silvers, and all bronzes which would cover 9 of the above 15 cases. Because, if test2 succeeds, we are left with 9 possible triads which can’t be covered with the 3 remaining tests. One way to split the above 15 triads is to put G1, G3, S1, S2, S3, B1, B2 in the bag for test2. We can see that that would cover 8 of the above 15 triads.
If test2 succeeds (bag glows), do test3 with G3, S1, S2, B1, B2. If test3 succeeds, test4 can determine the bad silver, and test5 can determine the bad bronze. If test3 fails, do test4 with G3, S3, B1, B2. If test4 succeeds, test5 can determine the bad bronze. If test4 fails, do test5 with G1, S3, B1. If test5 succeeds, we are done, and if it fails, the bad coins are G1, S3, B2.
If test2 fails, we are left with the following 7 possibilities (and 3 tests):
G3, S3, B3
G3, S2, B3
G3, S1, B3
G1, S3, B3
G2, S3, B1
G2, S3, B2
G2, S3, B3.
For test3, put G2, S3, B1, B2, B3. If test3 succeeds, we can determine the bad bronze within 2 more tests. If test3 fails, we are left with the following 4 possibilities (and 2 tests):
G3, S3, B3
G3, S2, B3
G3, S1, B3
G1, S3, B3
For test4, put G3, S1, S2, B3. If test4 succeeds, test5 can determine the bad silver. If test4 fails, we are left with the following 2 possibilities (and 1 test):
G3, S3, B3
G1, S3, B3
For test5, put G3, S3, B3. If test5 succeeds, that is the bad set of coins. Otherwise, G1, S3, B3 is the bad set.
With tons of patience, it should be possible to find a strategy when there are 10 coins of each type and 10 tests. Theoretically, there are 1024 possible outcomes from 10 tests, and we have 1000 possible counterfeit triads. We can also write a program to find the strategy (where a test that might leave too many remaining possibilities gets discarded). Non-adaptive strategies might also be possible, though the search space is huge for the 10-test case (even with pruning and heuristics). Even with the 5-test problem, there are 7 x 7 x 7 = 343 possible sets of coins (containing at least 1 of each type). That makes comb(343, 5), over 38 billion possible combinations of 5 tests (without thinking of symmetry and other pruning). We would be looking for one that would give a unique combination of test outcomes for each of the 27 possible triads. Large parts of the search would bail out early due to duplicate 5-test outcomes. Finding a non-adaptive strategy for the 10-test problem could be even more onerous.
28 August 2025, 3:25 pms_hskz2:
Tanya.
Thank you for introducing us to this puzzle.
BTW.
10*10*10=2*2*2*5*5*5
Therefore, it reduces to the following simple puzzle.
There are 5 coins of each kind, and you are allowed to test 7 times.
4 September 2025, 5:55 am