Generallizing independent weighings solution for coin weighing puzzle

Question

There is a puzzle that goes something like "you have $n$ coins with $m$ uses of s balance scale allowed; find out coin with the different weight" (normally given with $n=12$ and $m=3$).

Normally I see the solution given in a dependent form (ie. weight coins 1-4 against 5-8, if they balance do this, else do that). I understand how to generalize this dependent form for any $n$ such that I can minimize $m$.

However, I recently came upon an independent solution to this problem for $n=12$ and $m=3$. It relied on using the weightings as bits in a ternary number that would then identify the final coin. I copied the Wikipedia solution at the bottom.

I, however, don't understand how to generalize this independent solution (or really fully understand this one). How would one generalize this?

\// 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

Answer 1

First, you need to figure out the optimal number of weighings as a function of $n$. For any $k\in \mathbb N$, let $$ n(k)=\tfrac12(3^k-1) $$ It turns out that $k$ weighings are necessary and sufficient to find the fake among $n(k)$ coins. Conversely, given $n$ coins, then $k$ weighings are required, where $k$ is the smallest integer for which $n(k)\ge n$. From now on, $k$ will denote this smallest number of necessary weighings for the current $n$ under consideration.

A strategy for finding the fake among $n$ coins with $k$ weighings can be thought of as a $k\times n$ matrix whose entries are either $+1,-1$, or $0$. Each row represents a weighing, and each column represents a coin. During each weighing, the coins corresponding to $+1$ are weighed against those corresponding to $-1$, with the $0$ coins left off the scale. This weighing strategy must satisfy these two conditions, which are also sufficient:

• The sum of each row is zero, meaning an equal number of coins are in each pan for each weighing.

• For any two columns, $v$ and $w$, $v\neq w$ and $v\neq -w$. Indeed, if $v=w$, the strategy could not distinguish the case where $v$'s coin is fake and heavy from the case where $w$ is fake and heavy. Similarly, if $v=-w$, you cannot distinguish $v$ being heavy from $w$ being light.

For each $n\ge 3$, I will show how to construct a valid $k\times n$, weighing matrix, $A_n$.

• First, let us deal with the special case when $n$ is of the form $n(k)-1$ for some $k\in \mathbb N$, i.e. $n\in \{3,12,39,\dots\}$. The base case is $$ A_{n(2)-1} = A_3=\begin{bmatrix}+&-&0\\0&+&-\end{bmatrix} $$ Then, $A_{n(k)-1}$ is constructed recursively as follows: $$ A_{n(k)-1}=\left[\begin{array}{c|c|c|c|c|c} +&-&0&+\cdots + &-\cdots - &0\cdots 0 \\\hline \begin{array}{c}0\\\vdots\\0\end{array} & \begin{array}{c}+\\\vdots\\+\end{array} & \begin{array}{c}-\\\vdots\\-\end{array} & A_{n(k-1)-1} & A_{n(k-1)-1} & A_{n(k-1)-1} \end{array}\right] $$ You can prove by induction on $k$ that $A_{n(k)-1}$ is a valid weighing matrix, with rows summing to zero and columns pairwise distinct from their selves and their negatives. Furthermore, you can prove that $A_{n(k)-1}$ has no columns of all zeroes.

For example, here is the construction of $A_{12}=A_{n(3)-1}$ from the base case $A_3$: $$ A_{n(3)-1}=\begin{bmatrix} +&-&0&+&+&+&-&-&-&0&0&0\\ 0&+&-& \color{red}+&\color{red}-&\color{red}0& \color{green}+&\color{green}-&\color{green}0& \color{blue}+&\color{blue}-&\color{blue}0 \\ 0&+&-& \color{red}0&\color{red}+&\color{red}-& \color{green}0&\color{green}+&\color{green}-& \color{blue}0&\color{blue}+&\color{blue}- \end{bmatrix} $$

• Next, we construct $A_{n(k)}$, for each $k\ge 2$. Since $A_{n(k)-1}$ has no columns of zeroes, we can construct $A_{n(k)}$ by appending a column of zeroes to $A_{n(k)-1}$.

• Finally, for any other $n$ not yet covered before, we construct $A_n$ as follows. Every integer $n$ can be written in the form $n=2n'+n''$, where $n'$ and $n''$ are integers whose absolute difference is at most one (e.g, $14 = 2\cdot 5+4$). Then $$ A_n = \left[\begin{array}{c|c|c} ++\cdots + & --\cdots -& 00\cdots 0 \\\hline &&\\ A_{n'}&A_{n'}&A_{n''} \\ && \end{array}\right] $$There is one small caveat; when $n$ is of the form $n(k)+1$, e.g. $n\in \{14,41,122,\dots\}$, then matrices $A_{n'}$ and $A_{n''}$ have different numbers of rows. This is fixed by appending a row of zeroes to $A_{n''}$.

For this induction to work, you need base cases $A_{3},A_{4},\dots,A_{8}$. We already found $A_3$, and $A_4$ is obtained from $A_3$ by adding a column of zeroes. I leave it as a last puzzle to the reader to find valid matrices $A_n$ for $n\in \{5,6,7,8\}$. These will have $3$ rows and $n$ columns.