4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Just to note for the record: For three coins (k=1) you need three weighings. If there are two weighings they must both be one coin against another, and no two coins are equal. There must be a coin in common between the two weighings. If it is either heavier than the other two or lighter than the other two you know the common coin but can't compare the others. $\endgroup$ Apr 12 at 18:00
  • $\begingroup$ @MarkBennet - Yep. Another way to prove what you said is that for $c=3$, every weighing cannot have "balanced" as its result, and $2^2 < 6$. $\endgroup$
    – antkam
    Apr 12 at 18:38
  • $\begingroup$ Do you have a best result with three weighings? - !t is sometimes easier to build on number of weighings rather than number of coins. I've made some progress and can easily do five coins, but haven't yet turned proper attention to six. $\endgroup$ Apr 12 at 18:55
  • $\begingroup$ @MarkBennet - I havent thought about $3$ weighings until you mention it, but you're right that $5$ coins are doable. Meanwhile $6$ coins would have $6\times 5 = 30 > 3^3$ solutions so that would require $> 3$ weighings, and it's easy to do with $4$ weighings. $\endgroup$
    – antkam
    Apr 12 at 19:31
  • $\begingroup$ We are left also with the result that two weighings are useless - one will do two coins and three coins need three weighings. That in itself is a little unusual. $\endgroup$ Apr 12 at 19:36
4
$\begingroup$

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.

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

$\endgroup$
2
  • $\begingroup$ Very nice! I tried to do the recursion based on base-$3$ digits, and couldn't make it work. Love how your solution uses different ways of recursing based on whether the first weighing is equal or unequal! $\endgroup$
    – antkam
    Apr 13 at 0:46
  • 1
    $\begingroup$ Thank you! Actually, I'm usually terrible at these kinds of combinatorics problems, and I thought that the only way I could manage something was if there was a nice, clean, recursive proof. To get recursion, it was a natural idea to group coins by three, but I realized the importance of doing it in different ways when I realized that it just was untractable to let the two bad coins end up in the same bag (maybe there was an efficient way to find a result of "no bad coin", but testing all bags was prohibitive). So I tried to make splits that ensured that this didn't happen. $\endgroup$
    – Mindlack
    Apr 15 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.