Let $P_k$ (for $k \geq 2$) be the property: “there exists a strategy that works in $2k$ weightings, whose first move is comparing two groups of $3^{k-1}$ coins”.
We will show that $P_k \Rightarrow P_{k+1}$. We’ll see afterwards how $P_2$ is true.
Assume that $P_k$ holds, and let $c_1,\ldots,c_{3^{k+1}}$ be the coins. Our first weighting must be $c_1,\ldots,c_{3^k}$ against $c_{3^k+1},\ldots,c_{2\cdot 3^k}$.
- If the two are unequal, put, for each $1 \leq i \leq 3^k$, the coins $c_{3i-1},c_{3i-2},c_{3i}$ in a little bag $B_i$. Then $B_i$ satisfies the same properties as the coins (there’s a little trick here but it does work), but there are $3^k$ of them and we know the result of comparing $B_1,\ldots,B_{3^{k-1}}$ to $B_{3^{k-1}+1},\ldots,B_{2\cdot 3^k}$.
So, by $P_k$, we know that with $2k-1$ further weightings, we can find distinct indices $1\leq i,j \leq 3^k$ such that $B_i$ is the bad light bag (hence contains the lighter coin) and $B_j$ contains the heavier coin. With one weighting, you can find the lighter coin in $B_i$ (resp. the heavier coin in $B_j$) and that makes $2k+2$ weightings total.
- Now we assume that at the first weighting, the scales are balanced. We then construct $3^k$ bags of three coins, but with a different trick to ensure that there still is one lighter bag and one heavier bag: for $1 \leq i\leq 3^k$, $B_i$ is made with $c_{i+l\cdot 3^k}$, $0 \leq l \leq 2$. In $2k$ weightings, we can (by $P_k$) find distinct indices $1 \leq i, j\leq 3^k$ such that $B_i$ is the lighter bag while $B_j$ is the heavier one.
But using the results from the first weighting, it follows that the ordered pair $(\text{lighter coin, heavier coin})$ must be one of the $(c_{i+l\cdot 3^k},c_{j+l\cdot 3^k})$, with $0 \leq l \leq 2$ (ie the good and bad coins had to “compensate one another”). We only have one weighting left to determine which is the true possibility. To do that, we compare $c_i,c_{j+3^k}$ to $c_j,c_{i+3^k}$, and $Left$ is lighter (resp. heavier) than $Right$ iff the pair is $(c_i,c_j)$ (resp. $(c_{i+3^k},c_{j+3^k})$).
This ends our induction.
We still need to check $P_2$. Let use digits to denote our coins: $1,2,3,4,5,6,7,8,9$.
First we weigh $123$ against $456$. By symmetry we only need to consider the cases $123=456$ and $123<456$ ($<$ means “is lighter”).
If $123=456$, then both the heavier and lighter coins are in the same of the subsets $123,456,789$. Then weigh $1258$ against $3469$. If there is equality again, then the bad coins are either $12$ or $34$. Weigh $1$ against $2$, then $3$ against $4$ to know. If, on the other hand, (by symmetry again) $1258 < 3469$, then the possible $(\text{lighter, heavier})$ pairs are $13,23,54,56,89$. Then weigh $59$ against $84$: if it’s equal, then the possible pairs can only be $13,23$ and you can determine the right one with the last weighting. If $59<84$, then the right pair is $54$ or $56$ and you can again determine the right one with one last weighting. If $59>84$ then it’s $89$.
If $123<456$, this is much, much tighter (there are exactly $27$ possible cases and three weightings). Weigh $1245$ against $3678$. If there is equality, then the possible pairs (same order as ever) are $14,15,24,25,36,37,38,76,86$; then weigh $1463$ against $2578$. If there is equality, the possible pairs become $14,25,36$ and one weighting is enough to find the good one. If $1463<2578$, the possible pairs are $15,37,38$ and weighting $7$ against $5$ decides which is the good one. If $1463>2578$, the possible pairs are $24,76,86$ and weighing $7$ against $2$ decides the good one.
If $1245<3678$, the possible pairs are $16,17,18,26,27,28,19,29,96$. Weigh $178$ against $642$: if $178=642$, the possibilities are $17,18,26$ (decidable in one go), if $178<642$, the possibilities are $96,16,19$ (decidable by $61$ against $34$), if $178>642$, the possibilities are $27,28,29$, decidable in one go.
If $1245>3678$, the possibilities are $34,35,39,84,85,74,75,94,95$. Weigh $478$ against $253$. If there is equality, the possibilities are $47,84,35$ (decidable by $78$ against $35$), if $478<253$, the possibilities are $75,85,95$ (decidable in one go), if $478>253$, the possibilities are $34,94,95$ (decidable by $94$ against $12$).
And thus we’re done.
Best Answer
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$.
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.