Balance puzzle

Solution to the balance puzzle for 9 coins in 2 weighings, where the odd coin is lighter than the others – if the odd coin were heavier than the others, the upper two branches in each weighing decision are swapped

A well-known example has up to nine items, say coins (or balls), that are identical in weight except one, which is lighter than the others—a counterfeit (an oddball). The difference is perceptible only by weighing them on scale—but only the coins themselves can be weighed. How can one isolate the counterfeit coin with only two weighings?

A more complex version has twelve coins, eleven or twelve of which are identical. If one is different, we don't know whether it is heavier or lighter than the others. This time the balance may be used three times to determine if there is a unique coin—and if there is, to isolate it and determine its weight relative to the others. (This puzzle and its solution first appeared in an article in 1945.[2]) The problem has a simpler variant with three coins in two weighings, and a more complex variant with 39 coins in four weighings.

Given a population of 13 coins in which it is known that 1 of the 13 is different (mass) from the rest, it is simple to determine which coin it is with a balance and 3 tests as follows:

1) Subdivide the coins in to 2 groups of 4 coins and a third group with the remaining 5 coins.

2) Test 1, Test the 2 groups of 4 coins against each other:

a. If the coins balance, the odd coin is in the population of 5 and proceed to test 2a.

b. The odd coin is among the population of 8 coins, proceed in the same way as in the 12 coins problem.

3) Test 2a, Test 3 of the coins from the group of 5 coins against any 3 coins from the population of 8 coins:

a. If the 3 coins balance, then the odd coin is among the remaining population of 2 coins. Test one of the 2 coins against any other coin; if they balance, the odd coin is the last untested coin, if they do not balance, the odd coin is the current test coin.

b. If the 3 coins do not balance, then the odd coin is from this population of 3 coins. Pay attention to the direction of the balance swing (up means the odd coin is light, down means it is heavy). Remove one of the 3 coins, move another to the other side of the balance (remove all other coins from balance). If the balance evens out, the odd coin is the coin that was removed. If the balance switches direction, the odd coin is the one that was moved to the other side, otherwise, the odd coin is the coin that remained in place.

/// \\\

\// /\\
/\/ \/\
//\ \\/

\/– /\–
–\/ –/\
/–\ \–/

\\– //–
–\\ –//
\–\ /–/

/–– \––
–/– –\–
––/ ––\

–––

\// A light    /\\ A heavy
/\/ B light    \/\ B heavy
//\ C light    \\/ C heavy

\/– D light    /\– D heavy
–\/ E light    –/\ E heavy
/–\ F light    \–/ F heavy

\\– G light    //– G heavy
–\\ H light    –// H heavy
\–\ I light    /–/ I heavy

/–– J light    \–– J heavy
–/– K light    –\– K heavy
––/ L light    ––\ L heavy

––– M either lighter or heavier (13-coin case),
    or all coins weigh the same (12-coin case)

1st weighing:  left side: ADGI, right side: BCFJ
2nd weighing:  left side: BEGH, right side: ACDK
3rd weighing:  left side: CFHI, right side: ABEL

The generalization of this problem is described in Chudnov.[4]

Let ${\displaystyle \mathbb {R} ^{n}}$ be the ${\displaystyle n}$-dimensional Euclidean space and ${\displaystyle [\mathrm {e} ^{1},\mathrm {e} ^{2}]}$ be the inner product of vectors ${\displaystyle \mathrm {e} ^{1}}$ and ${\displaystyle \mathrm {e} ^{2}}$ from ${\displaystyle \mathbb {R} ^{n}.}$ For vectors ${\displaystyle \mathrm {e} =(e_{1},\dots ,e_{n})\in \mathbb {R} ^{n}}$ and subsets ${\displaystyle E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n},}$ the operations ${\displaystyle (\cdot )^{*}}$ and ${\displaystyle (\cdot )^{+}}$ are defined, respectively, as ${\displaystyle \mathrm {e} ^{*}=(sign(e_{i}))_{i}}$ ; ${\displaystyle E^{*}=\{(\mathrm {e} ^{j})^{*}\}}$, ${\displaystyle \mathrm {e} ^{+}=(|sign(e_{i})|)_{i}}$, ${\displaystyle E^{+}=\{(\mathrm {e} ^{j})^{+}\}.}$ By ${\displaystyle I^{n}}$ we shall denote the discrete [−1; 1]-cube in ${\displaystyle \mathbb {R} ^{n}}$; i.e., the set of all sequences of length ${\displaystyle n}$ over the alphabet ${\displaystyle I=\{-1,0,1\}}$ The set ${\displaystyle I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n}}$ is the discrete ball of radius ${\displaystyle t}$ (in the Hamming metric ${\displaystyle w()}$ ) with centre at the point ${\displaystyle \mathrm {0} .}$ Relative weights of ${\displaystyle n}$ objects are given by a vector ${\displaystyle \mathrm {x} =(x_{1},\dots ,x_{n})\in I^{n},}$ which defines the configurations of weights of the objects: the ${\displaystyle i}$th object has standard weight if ${\displaystyle x_{i}=0;}$ the weight of the ${\displaystyle i}$th object is greater (smaller) by a constant (unknown) value if ${\displaystyle x_{i}=1}$ (respectively, ${\displaystyle x_{i}=-1}$). The vector ${\displaystyle \mathrm {x} ^{+}}$ characterizes the types of objects: the standard type, the non-standard type (i.e., configurations of types), and it does not contain information about relative weights of non-standard objects.

A weighing (a check) is given by a vector ${\displaystyle \mathrm {h} \in I^{n};}$ the result of a weighing for a situation ${\displaystyle \mathrm {x} \in I^{n}}$ is ${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=sign([\mathrm {x} ;\mathrm {h} ]).} The weighing given by a vector ${\displaystyle \mathrm {h} =(h_{1},\dots ,h_{n})}$ has the following interpretation: for a given check the ${\displaystyle i}$th object participates in the weighing if ${\displaystyle h_{i}\neq 0}$; it is put on the left balance pan if ${\displaystyle h_{i}<0}$ and is put on the right pan if ${\displaystyle h_{i}>0.}$ For each weighing ${\displaystyle \mathrm {h} }$, both pans should contain the same number of objects: if on some pan the number of objects is smaller than as it should be, then it receives some ${\displaystyle r(\mathrm {h} )=[\mathrm {h} ;1,\dots ,1]}$ reference objects. The result of a weighing ${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )} describes the following cases: the balance if ${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=0} , the left pan outweighs the right one if ${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=-1} , and the right pan outweighs the left one if ${\displaystyle s(\mathrm {x}$ ;\mathrm {h} )=1.} The incompleteness of initial information about the distribution of weights of a group of objects is characterized by the set of admissible distributions of weights of objects ${\displaystyle Z\subseteq I^{n},}$ which is also called the set of admissible situations, the elements of ${\displaystyle z\in Z}$ are called admissible situations.

Each weighing ${\displaystyle \mathrm {h} }$ induces the partition of the set ${\displaystyle I^{n}}$ by the plane (hyperplane ) ${\displaystyle [\mathrm {x}$ ;\mathrm {h} ]=0} into three parts ${\displaystyle W(s|I^{n};\mathrm {h} )=\{\mathrm {x} \in I^{n}|s(\mathrm {x}$ ;\mathrm {h} )=s\}} , ${\displaystyle s\in I,}$ and defines the corresponding partition of the set ${\displaystyle Z=W(0|Z,\mathrm {h} )+W(1|Z,\mathrm {h} )+W(-1|Z,\mathrm {h} ),}$ where ${\displaystyle W(s|Z,\mathrm {h} )=W(s|I^{n},\mathrm {h} )\cap Z.}$

Definition 1. A weighing algorithm (WA) ${\displaystyle {\mathcal {A}}}$ of length ${\displaystyle m}$ is a sequence ${\displaystyle {\mathcal {A}}=<\mathrm {A} _{1},\dots ,\mathrm {A} _{m}>,}$ where ${\displaystyle \mathrm {A} _{j}:I^{j-1}\to I^{n}}$ is the function determining the check ${\displaystyle \mathrm {h} ^{j}=\mathrm {A} _{j}(s^{j-1});\mathrm {h} ^{j}\in I^{n},}$ at each ${\displaystyle j}$th step, ${\displaystyle j=1,2,\dots ,m,}$ of the algorithm from the results of ${\displaystyle \mathrm {s} ^{j-1}=(s_{1},\dots ,s_{j-1})\in I^{j-1}}$ weighings at the previous steps ( ${\displaystyle \mathrm {h} ^{1}=\mathrm {A} _{1}()}$ is a given initial check).

Let ${\displaystyle S(Z,{\mathcal {A}})}$ be the set of all ${\displaystyle (Z,{\mathcal {A}})}$-syndromes and ${\displaystyle W(s|{\mathcal {A}})\subseteq I}$ be the set of situations with the same syndrome ${\displaystyle s}$; i.e., ${\displaystyle W(s|{\mathcal {A}})=\{\mathrm {z} \in I^{m}|s(z|{\mathcal {A}})=s\}}$; ${\displaystyle W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z.}$

Definition 2. A WA ${\displaystyle {\mathcal {A}}}$ is said to: a) identify the situations in a set ${\displaystyle Z}$ if the condition ${\displaystyle |W(s|Z,{\mathcal {A}})|=1}$ is satisfied for all ${\displaystyle s\in S(Z{\mathcal {A}});}$ b) identify the types of objects in a set ${\displaystyle Z}$ if the condition ${\displaystyle |W^{+}(s|Z{\mathcal {A}})|=1}$ is satisfied for all ${\displaystyle s\in S(Z{\mathcal {A}}).}$

It is proved in [4] that for so-called suitable sets ${\displaystyle Z}$ an algorithm of identification the types identifies also the situations in ${\displaystyle Z.}$

As an example the perfect dynamic (two-cascade) algorithms with parameters ${\displaystyle n=11,m=5,t=2}$ are constructed in [4] which correspond to the parameters of the perfect ternary Golay code (Virtakallio-Golay code). At the same time, it is established that a static WA (i.e. weighting code) with the same parameters does not exist.

Each of these algorithms using 5 weighings finds among 11 coins up to two counterfeit coins which could be heavier or lighter than real coins by the same value. In this case the uncertainty domain (the set of admissible situations) contains ${\displaystyle 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5}}$ situations, i.e. the constructed WA lies on the Hamming bound for ${\displaystyle t=2}$ and in this sense is perfect.

To date it is not known whether there are other perfect WA that identify the situations in ${\displaystyle I_{t}^{n}}$ for some values of ${\displaystyle n,t}$. Moreover, it is not known whether for some ${\displaystyle t>2}$ there exist solutions for the equation ${\displaystyle \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m}}$ (corresponding to the Hamming bound for ternary codes) which is, obviously, necessary for the existence of a perfect WA. It is only known that for ${\displaystyle t=1}$ there are no perfect WA, and for ${\displaystyle t=2}$ this equation has the unique nontrivial solution ${\displaystyle n=11,m=5}$ which determines the parameters of the constructed perfect WA.

Eliran Sabag invented this puzzle. There are N indistinguishable coins, one of which is fake (it is not known whether it is heavier or lighter than the genuine coins, which all weigh the same). There are two balance scales that can be used in parallel. Each weighing lasts three minute. What is the largest number of coins N for which it is possible to find the fake coin in ten minutes?[5]

• A playable example of the second puzzle
• Two-pan balance and generalized counterfeit coin problem