While reading excellent *Professor Stewart’s Cabinet of Mathematical Curiosities* I came across the 12 coins problem (again). This problem is usually stated like this: you have 12 coins out of which a single one is a counterfeit, either lighter or heavier than the regular ones. You have access to a balance scale and need to determine which coin is fake and if it weighs more or less compared to genuine coins. You only have three weighings to accomplish this.

I must have seen this problem before and maybe even have solved this previously, however I could not remember the details of the answer. So I started anew especially as I was seeing a way to solve this neatly.

Obviously in each of three weighings every coin might be put on the left pan, right pan, or put away. Let’s code the left pan by 1, right pan by 2 and off the scale as 0. Obviously to differentiate between the coins each needs to have a different pattern of being placed into the left, right and no pan. For three weighings there are 3^3=27 such codes available, although (0, 0, 0) or 000 is not acceptable since we need to measure each coins at least once to determine if it’s heavier or lighter. So we have 001, 002, 010, 011, 012, 020…, …, 221, 222 to choose from.

Conveniently if we assume that each of the coins is weighed exactly twice we will end up with twelve available codes:

1: 110 2: 120 3: 210 4: 220 5: 101 6: 102 7: 201 8: 202 9: 011 10: 012 11: 021 12: 022

For example the 1st coin would be put on the left pan in both first and second weighing step and put away for the third one. If the left pan would be heavier in both 1st and 2nd attempt and there would be an equilibrium in the third one, the first coin would be a heavier counterfeit. Or would it? Equally the 4th coin might be a lighter counterfeit since it was placed in the pan opposite to the 1st coin. My assumption was wrong. The code assignment as given above is NOT a correct solution.

Given this failure I resorted to a more clumsy solution involving a decision tree. It involved weighing a different number of coins each time, which convinced me that there must not be a solution that has 4 +4 coins on the scale each time. Having completed this I looked up the answer in Professor Stewart’s book. To my astonishment he gave a neat answer basing on a coding similar to mine! How was it even possible? Oh, there was a detail I overlooked. You get more usable codes if you weigh some coins just once and some three times!

There are some questions that arise at this point.

How to find a coding that will always give a correct solution?

Is the solution given in the book the only such coding? (Up to the order and left/right symmetry).

Is there a coding that puts only 1, 2, 3, 5 or 6 coins into each pan at some weighing step?

Let’s find out the size of the problem first. We have 27-1=26 codes to choose from and we need to assign one to each coin. The number of such assignments is C(26, 12)=9657700 (C stands for combinations, binomial coefficient). This is small enough to check them all by brute force.

An assignment must fulfill some conditions to be considered a correct solution. First of all, there must be equal numbers of coins in both pans at each of three weighing steps. So if 4 codes have “1′ as the first digit, which stands for the left scale pan in the first step, the remaining chosen codes must have 4 codes starting with “2″ (right pan in the first step) and the remaining four require “0″. Function equal_counts verifies this condition.

The other important condition is the “no symmetric coins” as shown in the example of my failed coding above. If a coin is given a code of 112 (left, left, right) any other coin cannot be assigned 221 (right, right, left). Otherwise you would not be able to determine which of the two is a counterfeit and whether it is heaver or lighter. This is checked by has_symmetric_coins function.

The brute force method finds the correct codings in less than a minute on a modern laptop. After removing duplicates – rejecting left/right symmetrical solutions and these solutions where only the order of weighing steps changes – there are 26 unique solutions left. What’s interesting each of them has 4+4 coins weighed at every step; this means that e.g. weighing 5+5 in any step would destroy too much information. An example solution is shown here. As you see the first coin is weighed only once, on the left scale pan in the third batch. On the other hand coin number 12 is weighed three times, as right, right, left. Thus if the scale would balance towards right, right and left in the three steps, the 12th coin would be a heavier fake; balance towards left, left and right would mean 12th coin is lighter, while balance towards left, left and equal (110, opposite of 220) would mean 11th coin is lighter. And so on.

1: 001 2: 010 3: 011 4: 012 5: 100 6: 102 7: 121 8: 122 9: 202 10: 210 11: 220 12: 221

The brute force program is given below. I’m sure there must be a more sophisticated and faster algorithm. Finding it is left as an exercise for the reader.

import itertools left_right_map = {} def equal_counts(tuple_of_tuples, weigh_cnt): # weigh_cnt == len(tuple_of_tuples[0]) for i in range(weigh_cnt): left = sum([ 1 for x in tuple_of_tuples if x[i] == 1 ]) right = sum([ 1 for x in tuple_of_tuples if x[i] == 2 ]) if left != right: return False return True def has_symmetric_coins(tuple_of_tuples, weigh_cnt): global left_right_map m = [ 0, 2, 1] if len(left_right_map) == 0: for t in itertools.product([0, 1, 2], repeat=weigh_cnt): equivalent_t = tuple([m[x] for x in t]) left_right_map[t] = equivalent_t for t in tuple_of_tuples: equivalent_t = left_right_map[t] if equivalent_t in tuple_of_tuples: return True return False def check(coins, weigh_cnt): pos = [ t for t in itertools.product([0, 1, 2], repeat=weigh_cnt) if sum(t) > 0 and sum(t) < weigh_cnt * 2 # remove no weighing and always right cases ] i = 0 sol = [] for t in itertools.combinations(pos, coins): i += 1 if i % 100000 == 0: print(i) if not equal_counts(t, weigh_cnt): continue if has_symmetric_coins(t, weigh_cnt): continue sol.append(t) print(i, len(sol), t) return sol def is_unique_solution(tot, solutions, weigh_cnt): lrmaps = [[0, 1, 2], [ 0, 2, 1]] # 0: no change, 1: 1->2, 2->1 for pm in itertools.permutations(range(weigh_cnt)): for lrmap in lrmaps: eqsol = [] for t in tot: equivalent_t = tuple([ lrmap[t[pm[i]]] for i in range(weigh_cnt) ]) eqsol.append(equivalent_t) eqsol.sort() eqsol = tuple(eqsol) if eqsol in solutions: return False return True def main(): COINS = 12 COUNT = 3 solutions = check(COINS, COUNT) uniq = [] for sol in solutions: if is_unique_solution(sol, uniq, COUNT): uniq.append(sol) print(len(uniq)) for u in uniq: print(u) for i in range(COUNT): print(i + 1, ":", [t[i] for t in u].count(0), end=", ") print() if __name__ == "__main__": main()