Difficult coin weighing puzzle: 14 coins, 1 fake (heavier or lighter), 3 pre-determined weighings

Question

This recent question reminds me of a coin weighing puzzle I learned many years ago. It is one of the hardest puzzles of this kind that I know. I will post my solution in a few days, and meanwhile hopefully someone may enjoy it. (My apologies if this is a repeat, but I searched and could not find this exact version.)

---

There are $14$ suspect coins, $13$ of which are good and have the same weight, and the last one is bad and have a different weight (heavier or lighter). In addition, you have a $15$th coin that is known to be good.

You want to find which suspect coin is bad, and as much as possible (see below), whether it is heavier or lighter. There are therefore $28$ possible answers: $14$ suspects $\times \{heavier, lighter\}$.

You are allowed $3$ weighings on a balance. Now of course, $3$ weighings only give you $3^3 = 27$ possible outcomes, so you cannot fully distinguish all $28$ answers. The requirement is that:

• $26$ of the $27$ outcomes must lead to a unique answer (which coin is bad and whether it is heavier or lighter)

• while the last outcome must lead to knowing which coin is bad, but without knowing if it's heavier or lighter (i.e. it lumps together the $2$ answers for that coin).

The above puzzle would be difficult enough, but here's the final twist: What coins to use in a weighing cannot depend on the results of previous weighings.

To be more precise, label the suspect coins ABCDEFGHIJKLMN and the known-to-be-good coin X. Before you begin, you must write down what two subsets of coins are involved in each of the $3$ weighings, e.g. ABCDX-EFGHN, IJKL-MNAB, CDEFGH-IJKLMN. This way, your second weighing IJKL-MNAB is pre-determined and cannot depend on the result of the first weighing ABCDX >/=/< EFGHN, etc. (Indeed, you can now do the $3$ weighings in any order.)

Can you find such a set of $3$ pre-determined weighings that meets the requirement?

---

HINT #1: The outcome $(=, =, =)$, i.e. all $3$ weighings being equal, can only happen if the bad coin is not used in any weighing at all. This corresponds to the 2nd bullet of the requirement. I.e. in any correct solution, there is exactly one coin that is unused in any weighing, and the outcome $(=,=,=)$ maps to this coin being bad, but without knowing if the coin is heavier or lighter.

HINT #2: Let the $28$ answers be $S = \{A+, A-, B+, B-, ..., N+, N-\}$ where $+$ and $-$ mean heavier and lighter respectively. Meanwhile, the $27$ outcomes form a $3 \times 3 \times 3$ cube, which we can denote $T = \{-1, 0, +1\}^3$, where $-1, 0, +1$ denote the left side of the balance being lighter, equal, or heavier. We need to find a mapping $f: S \to T$ with these properties:

• Hint #1 already shows that $f(N+) = f(N-) = (0,0,0)$.
• The remaining $26$ answers and $26$ outcomes must map bijectively.
• Pre-determined weighings $\implies f(A+)$ and $f(A-)$ are related in a certain way. How?
• What other constraints do we need on $f$?

Answer 1

Suppose a triple of weighing results determines a coin. If a weighing result is "equal" then the coin did not appear in that weighing. Otherwise, the coin appeared on either the "less" side of each weighing or the "greater" side of each weighing depending on whether the coin was lighter or heavier.

For each coin, then, choose a distinct weighing result pattern that will determine that coin. (Weighing result patterns that are completely flipped must identify the same coin with the opposite weight, so we won't use these.)

A < = =
B = < =
C = = <
D < < =
E < = <
F = < <
G < > =
H < = >
I = < >
J < < <
K < < >
L < > <
M > < <
N = = =

Then we know exactly how to assemble each weighing (ie A appears in the first weighing only; G appears on opposite sides of the first two weighings; J appears on the same side of all weighings; etc) except that we don't know which side to put the coins on, but deciding the sides turns out to be easy, as we merely need to balance the number of coins in each weighing. Coin X (the known good coin) is needed because there are otherwise nine coins involved in each weighing. We will not be able to distinguish between coin N being lighter or heavier.

One solution is

AGJKL-DEHMX
BIJKM-DFGLX
CHJLM-EFIKX

Answer 2

Now that @tehtmi has posted a valid solution, here's my slightly different approach.

As I alluded to in Hint #2, the interesting thing about pre-determined weighings is: $f(A+) = -f(A-)$, i.e. the two answers $A+, A-$ must have opposite outcomes in all $3$ weighings. (The opposite of "balance" aka "$=$" aka $0$ is of course balance.) This is generally not true in a solution where a later weighing depends on the result of a previous weighing.

So anyway it becomes a matter of assigning $13$ $+$'s and $13$ $-$'s to the $26$ non-center outcomes in the overall $3 \times 3 \times 3$ cube, such that:

• Constraint 1: For any pair of outcomes $y,z$ which are reflections across the center, $y,z$ must have opposite signs.

In this cube, the $6$ faces ($3$ pairs of faces) represent the $3$ weighings. If we had access to an unlimited number of known-to-be-good coins (in fact $9$ is sufficient), then Constraint 1 is sufficient. Say the top face has $A+, B+, C+, D+, E+, F+, G+, H+, I+$, then the bottom face has $A-, B-, \dots, I-$ and the weighing would be those $9$ coins vs $9$ known-to-be-good coins.

But we only have $1$ known-to-be-good coin, and this translates to:

• Constraint 2: Each of the $6$ faces (each face being $9$ outcomes) must consist of $5$ of one sign, and $4$ of another. The weighing will be the $5$ vs the $4$ plus the known-good coin.

At this point, the problem becomes a small coloring puzzle that needs to be solved by trial and error. One solution is shown below (the three separate $3 \times 3$ squares represent the top, middle, bottom layers of the cube):

+ - +
- + +
+ - -

- + -
+ ? -
+ - +

+ + -
- - +
- + -

and just for completeness, here is how to assign letters to them to match exactly tehtmi's solution:

J+ F- M+
E- C+ H+
L+ I- K-

D- B+ G-
A+ N? A-
G+ B- D+

K+ I+ L-
H- C- E+
M- F+ J-

where e.g. the left-face-right-face-pair is the weighing JLAGK-EDHMX, and the top-face-bottom-face-pair is the weighing LHCMJ-KIEFX, etc.

---

BTW, this result is equivalent to the following result:

• If there were only $13$ suspect coins (and $1$ bad as usual), plus a single known-good coin, then in $3$ pre-determined weighings we can find the bad coin and tell if it's heavier/lighter. After all, we did not even use the $14$th coin N in the solution above.

which is in turn strictly stronger than this classic result:

• The classic $12$-coin puzzle is often posed without the constraint of pre-determined weighings, but it can in fact be solved using pre-determined weighings. In this classic, there is no known-good coin. However, in our solution J (a suspect) and X (the known-good coin) appear in all $3$ weighings and always on opposite sides. So Eliminating both of them solves the classic puzzle with $3$ pre-determined weighings of $4$-vs-$4$ each.

Answer 3

There is a very simple description of an optimal predetermined weighing strategy for any number of coins $n\ge 1$. This uses the balanced ternary system, which I describe now. Every positive integer $n$ can be written uniquely in the form $$ n=\sum_{i=0}^\infty b_i3^i,\qquad b_i\in\{-1,0,+1\}\text{ for }i\in\mathbb N, \text{only finitely many $b_i\neq 0$.} $$ For example, $25=1\cdot 3^3+0\cdot 3^2+(-1)\cdot 3^1+1.$ Using $+$ as the symbol for the digit $1$ and $-$ for the digit zero, we would write $25$ in balanced ternary, with infinitely many leading zeroes, as $$ 25=\cdots000+0-+ $$ Now, consider the following transformation on this infinite sequence of $\pm$s and $0$s; negate each symbol which has an odd number of zeroes to its right. The result to the above example is $$ 25\bowtie\cdots 000\color{red}-0-+ $$ I call this the twisted ternary representation of $25$. Next, arrange all of these infinite sequences into an infinite matrix, where the digits which are were negated when converting to twisted ternary are highlighted in red.

$$ \def\r{\color{red}} \begin{matrix} 0 & \bowtie & \cdots & 0 & 0 & 0 & 0\\ 1 & \bowtie & \cdots & 0 & 0 & 0 & +\\ 2 & \bowtie & \cdots & 0 & 0 & + & -\\ 3 & \bowtie & \cdots & 0 & 0 & \r - & 0\\ 4 & \bowtie & \cdots & 0 & 0 & + & +\\ 5 & \bowtie & \cdots & 0 & + & - & -\\ 6 & \bowtie & \cdots & 0 & \r - & \r + & 0\\ 7 & \bowtie & \cdots & 0 & + & - & +\\ 8 & \bowtie & \cdots & 0 & \r - & 0 & -\\ 9 & \bowtie & \cdots & 0 & + & 0 & 0\\ 10 & \bowtie & \cdots & 0 & \r - & 0 & +\\ 11 & \bowtie & \cdots & 0 & + & + & -\\ 12 & \bowtie & \cdots & 0 & \r - & \r - & 0\\ 13 & \bowtie & \cdots & 0 & + & + & +\\ 14 & \bowtie & \cdots & + & - & - & -\\ \vdots &&\vdots &&&\vdots \end{matrix} $$ To find the weighing strategy for $n$ coins, number the coins from $0$ to $n-1$. For each column of that matrix, weigh the coins corresponding to row labels of the $+$'s in that columns, against the coins corresponding to $-$'s (ignoring the infinitely many leading columns whose entries $0$ to $n-1$ are all zero). You may also need to add the reference coin to one side to equalize these groups.

For your problem of $n=14$, the weighings are (where $R$ denotes reference coin):

• $1,4,7,10,13\quad $ vs $\quad 2,5,8,11,R$
• $2,4,6,11,13\quad $ vs $\quad 3,5,7,12,R$
• $5,7,9,11,13\quad $ vs $\quad 6,8,10,12,R$.