6
$\begingroup$

I was recently asked to solve the classic twelve coins balance problem:

You are given twelve coins, eleven of which are equal in weight and one of which is either heavier or lighter than the other eleven. Using a typical balance scale, can you find the odd one out in only three uses of the scale?

I managed to find a solution to the problem the next day by trial and error (I won’t post in case anyone new to it wants to try their hand at it!) but after a quick Google search and a discussion with a friend who has also solved it, I realized there are multiple solutions (of which, interestingly enough, mine seems the most clunky and cluttered).

Of course, since there are 24 (12 coins x 2 conditions - lighter or heavier) possible odd coin scenarios, a solution to the problem must be in the form of a decision tree that will find that odd coin in all 24 scenarios. I began to wonder how many possible such trees (unique solutions to the twelve coin problem) there were. It seems there would be a mathematical way to prove/discover how many possible distinct solutions there are, perhaps by counting how much information is needed at the end and working backward, assigning values to each scenario and its informational value (how many coins it narrows it down to, whether it gives you useful info on heaviness/lightness, etc.) I currently know of at least three, possibly four solutions (mine and two or three others). Is there a mathematical way to find out how many solutions (unique decision trees which find the odd coin in all 24 cases) are possible?

$\endgroup$
4
  • $\begingroup$ Among your solutions, did you know there are non-adaptive ones, where you assign the coins to be weighed and how in advance of performing any weighings? $\endgroup$
    – xnor
    Commented Aug 20, 2023 at 2:58
  • $\begingroup$ @xnor no, I didn’t know that! Mine and all the others I’ve come across are adaptive. $\endgroup$
    – Kevin H
    Commented Aug 21, 2023 at 1:47
  • $\begingroup$ I’ve also wondered if there are any possible solutions in which three weighings tells you the odd coin out, but not whether it’s heavier or lighter. My solution gives you both in three weighings every time. $\endgroup$
    – Kevin H
    Commented Aug 21, 2023 at 1:49
  • $\begingroup$ There's these non-adaptive solutions that are very cool: puzzling.stackexchange.com/a/22138/15942 $\endgroup$
    – Dr Xorile
    Commented Aug 22, 2023 at 2:04

2 Answers 2

5
$\begingroup$

I have an answer to the non-adaptive version of the problem, that is, the version where one must declare ahead of time all three weighings one will perform, and their algorithm is not allowed to change in response to information learned during its execution. This answer is:

There are exactly seven non-adaptive algorithms up to symmetries (see section three for which "symmetries" we are considering, exactly). They are enumerated below:

1. [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([1,3,6,12],[4,5,9,11])]
2. [([1,2,3,4],[5,6,7,8]),([1,5,9,10],[2,6,7,11]),([3,6,9,11],[4,5,7,12])]
3. [([1,2,3,4],[5,6,7,8]),([1,5,6,7],[8,9,10,11]),([2,5,9,12],[3,6,8,10])]
4. [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,12],[3,5,9,10])]
5. [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([1,2,7,10],[3,5,11,12])]
6. [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,9,10],[3,5,8,12])]
7. [([1,2,3,4],[5,6,7,8]),([1,5,6,9],[7,8,10,11]),([2,7,10,12],[3,5,8,11])]

For example, the first algorithm is "in the first round, place coins 1, 2, 3, and 4 on the left balance, and 5, 6, 7, 8 on the right; in the second round, place coins 1, 5, 9, 10 on the left, and 2, 6, 7, 11 on the right; and in the final round, place coins 1, 3, 6, 12 on the left, and 4, 5, 9, 11 on the right."

How do we know these algorithms work?

This is the easy part. To describe a valid algorithm, you need nothing more than the weighings, and the assurance that each of the 24 possible input cases (12 coins, each of which may either be lighter or heavier than the rest) yield different results. For example, for the first algorithm above, the results are:

Coin 1 is Lighter ---> [Lighter,Lighter,Lighter]
Coin 1 is Heavier ---> [Heavier,Heavier,Heavier]
Coin 2 is Lighter ---> [Lighter,Heavier,Equal]
Coin 2 is Heavier ---> [Heavier,Lighter,Equal]
Coin 3 is Lighter ---> [Lighter,Equal,Lighter]
Coin 3 is Heavier ---> [Heavier,Equal,Heavier]
Coin 4 is Lighter ---> [Lighter,Equal,Heavier]
Coin 4 is Heavier ---> [Heavier,Equal,Lighter]
Coin 5 is Lighter ---> [Heavier,Lighter,Heavier]
Coin 5 is Heavier ---> [Lighter,Heavier,Lighter]
Coin 6 is Lighter ---> [Heavier,Heavier,Lighter]
Coin 6 is Heavier ---> [Lighter,Lighter,Heavier]
Coin 7 is Lighter ---> [Heavier,Heavier,Equal]
Coin 7 is Heavier ---> [Lighter,Lighter,Equal]
Coin 8 is Lighter ---> [Heavier,Equal,Equal]
Coin 8 is Heavier ---> [Lighter,Equal,Equal]
Coin 9 is Lighter ---> [Equal,Lighter,Heavier]
Coin 9 is Heavier ---> [Equal,Heavier,Lighter]
Coin 10 is Lighter ---> [Equal,Lighter,Equal]
Coin 10 is Heavier ---> [Equal,Heavier,Equal]
Coin 11 is Lighter ---> [Equal,Heavier,Heavier]
Coin 11 is Heavier ---> [Equal,Lighter,Lighter]
Coin 12 is Lighter ---> [Equal,Equal,Lighter]
Coin 12 is Heavier ---> [Equal,Equal,Heavier]

As such, an algorithm need only include the data for instructions, not deductions.

In what sense are these the only non-adaptive algorithms?

This is a slightly subjective part of the problem. For example, the algorithm [([1,2,3,4],[5,6,7,8]),([1,2,5,9],[3,6,10,11]),([1,4,7,10],[2,3,11,12])] does not feature in the above list, and I would be surprised to find someone who could intuitively see a relation between this one and any of the above seven. Yet, if you apply the permutation (1 5 3 7) (2 8 4 6) (9 12 11 10) (cycle notation) to the coins of the former, switch the steps up, and mirror the scale at some steps, you will get Algorithm 6 back.

So that was my basis for deciding when two algorithms were "the same": if and only if they could be related to one another by a sequence of (1) a relabeling of the coins, (2) a reordering of the three steps, and (3) potential mirrorings of the scale balance in each step.

How did you find these seven, and how can we confirm there are no more?

It was necessarily computer-aided, but it was intricate. Haskell code is here, but it's a bit messy, and I encourage anyone to corroborate my results.

One can see that there are 73,788 pairs of disjoint, nonempty subsets of {1, 2, ..., 12} of equal cardinality (of which 34,650 are of cardinality 4, if you can rigorously justify why only these should be considered; I cannot, personally, but my methods do not rely on this). As such, the number of isomorphism classes of non-adaptive algorithms can be estimated: $$\frac{(73788)^3}{(12!)(3!)(2!)^3} \approx 1.7 \times 10^4$$ which is within the realm of brute-forcing even before pruning out the many obviously nonviable candidates. However, I don't know a canonical and efficient way of enumerating these and only these candidates. The numerator itself is in the hundreds of trillions.

The method employed in my code relies on the notion of "indistinguishability classes" to generate mostly-deduplicated algorithms in a sort of standard form. For example, before the very first step, every coin is indistinguishable from the others, and after symmetries the algorithm's first step will have to be "put coins 1, ..., n on the left, and n+1, ..., m on the right" for 1 <= n < m <= 12. After this step with, say, n=3 and m=6, the indistinguishability classes are [1,2,3], [4,5,6], [7,8,9,10,11,12]. I proceed with generating algorithms along these lines, and selecting only those that end up with 12 indistinguishability classes (singletons). After filtering for those that described truly valid algorithms, I wound up with 130 candidates.

In order to bring these 130 down to 7, I had to manually check for the resulting isomorphism classes. Seeing as there are about half a billion permutations of the 12 coins (and the step-order/scale mirror symmetries are easy to detect), it's possible this could be done entirely brute force. Nonetheless I reduced the problem to a "subset isomorphism problem," which is to answer, "Given subsets X_1, ..., X_n and Y_1, ..., Y_n, does there exist a permutation that maps X_i to Y_i for all i?" This problem can be solved by a more efficient depth-first search.

So what about the adaptive version of the problem?

Obviously there will be many more solutions in the adaptive case. An adaptive algorithm can be uniquely described by a flowchart of 1 + 3 + 9 = 13 weighings, which will explode the search space far beyond the 3 weighings for the non-adaptive case. A very rough estimate: If we assume only 4-coin weighings, fix the first step to be "weigh coins 1-4 against coins 5-8," and then assume every other weighing to be one among the 34,650 mentioned above (granted this is an overestimate), we get
$$\frac{(34650)^{12}}{(12!)(2!)^{12}} \approx 1.5 \times 10^{42}$$
You'll notice I excluded the step-order invariance in the denominator, and this is one point where I consider the problem to be a bit ill-defined. In general it makes no sense to swap the step-order of an adaptive algorithm, but non-adaptive algorithms embed as a subset of the adaptive algorithms, so does it make sense that we're allowed to swap the order of steps "only sometimes"? I think a clearer formulation of the isomorphism classes of the adaptive strategy case is necessary before one embarks on the journey to generate and isolate them, if it's even computationally feasible.

$\endgroup$
0
$\begingroup$

Note that there are many (I believe 10) possible solutions in which three non adaptive weighings tells you the odd coin out, but not whether it’s heavier or lighter.

e.g.

1,2,3,4 - 5,6,7,8 1,2,7,10 - 3,4,5,9
1,3,8,11 - 2,4,6,9 (3 times balanced means 12 is the fake)

Note also that if heavy light does not matter, it is actually the '13 coins problem'; the solutions in the accepted answer work with 13 coins; if all three measurements are balanced, the 13th coin is fake.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.