Coin weighing puzzle: one heavy coin, one light coin, which together weigh the same as two normal coins

Question

My question was inspired by this previous question.

There are $c = 3^k$ coins where $k \ge 2$. Among these coins:

• $c-2$ of them are good and weigh the same.
• The remaining $2$ coins are bad: one of them is heavier than a good coin, and the other is lighter than a good coin.

The problem is to identify both bad coins (including which is heavy, which is light) using weighings on a balance.

Importantly (and unlike the previous question): the two bad coins together weigh the same as two good coins. I.e., if the two bad coins are on one side of a weighing, and two good coins are on the other side, then the result would be balanced.

There are $c(c-1)$ possible solutions. Since $3^{2k-1} = c(c/3) < c(c-1) < c^2 = 3^{2k}$, we know that $2k$ weighings are necessary.

My question: Are $2k$ weighings sufficient?

I have a solution for $c = 9$, where indeed $2k = 4$ weighings are sufficient. I will post this in a few days, so that others can try their hands on it (both for fun, and also because I don't want to bias people one way or another initially). My solution is pretty tedious, and I could not generalize it to higher $k$.

If, like me, you can solve the $c=9$ case but cannot generalize to higher $k$, please feel free to post you (partial) solution so we can perhaps compare approaches.

Answer 1

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}$.

1. 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.

2. 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.