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
Using only weighings with one coin on each side, one can prove that the ordering can be determined with seven weighings:
The way to figure this out was:
Without loss of generality, one can assume that the first weighing tells you that coin $B$ is heavier than coin $A$ (written as $B>A$). Then there are only two classes of choices of next weighings:
(1) Weigh coin $C$ against coin $A$ (or any equivalent weighing against an already-weighed coin): Here, a possible result is $C>A$ which leaves 40 allowed orders. Since each weighing provides only one bit of information, discerning among $40$ orders requires at least six weighings, for a total of eight.
(2) Weigh coin $C$ against coin $D$ (or any equivalent weighing of two not-yet-weighed coins): Then there are three classs of next weighing choices available.
(2a) If the third weighing is $E$ versus $D$ (or any of the already-weighed coins) then one possibility says that $E<D$, which leaves $20$ allowed orders, requiring at least $5$ further weighings, for a total of eight.
(2b) If the third weighing is $D$ versus $A$ (or equivalently $B$ versus $C$) then the answer $D>A$ leaves $25$ possible orderings (slotting $E$ into any of $5$ positions, with the first four ordered $DCBA, DBCA, DBAC, BDAC$ or $BDCA$) which again requires at least $5$ further weighings, for a total of at least eight.
(2c) If the third weighing is $D$ versus $B$ (or equivalently $A$ versus $C$) then the answer must be equivalent to $D>B$. So $D>B>A$ and you can slot $C$ into any of three positions (but not into $C>D$) and then $E$ into any of $5$ positions. With $15$ allowed possibilities, it might still be possible to discern the ordering in only four more weighings.
So assume we have (in three weighings) $D>B>A$ and $D>C$. The next weighing needs to involve coin $E$ because if we weigh $C$ against $B$ or $A$ there will be some chance of leaving two remaining positions possible for $C$, thus two times five remaining allowed orderings, which cannot be disambiguated in only three further weighings.
3a) Say the next choice (the 4th weighing) is to weigh $E$ versus $B$ (this is the obvious one to try because $D>B>A$). Then if we find $E<B$ we will end up knowing that $D>B>E>A$ or $D>B>A>E$. We spend our fifth weighing on $A$ versus $E$ to fully order those four. Since we know $D>C$ we can now find where $C$ belongs in only two more weighings (starting from weighing $C$ against the second lightest of the others), for a total of seven weighings.
Similarly, if we find $E>B$ we will end up knowing that $D>E>B>A$ or $E>D>B>A$. We spend our fifth weighing on $D$ versus $E$ to fully order those four. And again we can properly place $$ in two more wiehings, for a total of seven.
(3b) If the fourth weighing were to be $E$ versus $A$ or $E$ versus $D$, then we would require eight weighings in the end.