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

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$?

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

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.