Weighting coins

Question

Six coins of different weights are given, and it is known that the first coin is lighter than the second, the third is lighter than the fourth, and the fourth is lighter than the fifth. There are scales that allow you to compare any two coins by weight. Prove that in order to order all coins by weight, 7 weighings are necessary and sufficient.

ATTEMPT: By the condition of the task, there are exactly 60 configurations with such data. But $5<\log(60)<6$, so there is a lower estimate on 6 weightings. Help please.

Answer 1

First, we prove that $7$ comparisons is sufficient. Here's the algorithm:

• We shall spend at most $4$ comparisons in the following process: the variables $A$ and $B$ will be chosen from $\{1, 2\}$ and $\{3, 4, 5\}$ respectively. Initialize $A = 1$ and $B = 3$. Initialize the list $L$ to be empty. Compare $A$ and $B$. Append the heavier of the two to $L$, then increment it if possible. If not (i.e. when $A = 2$ is heavier or when $B = 5$ is the heavier) then append the other value to $L$ as well. Prove that this process sorts the first $5$ coins in descending order of weights.
• Perform binary search to place the $6$th coin in the correct place. This will take at most $3$ comparisons since $\lceil \log_2(5) \rceil = 3$. Thus, the algorithm will take a total of at most $4 + 3 = 7$ comparisons.

Next, we show that $7$ comparisons is necessary. As you pointed out, there are $60$ initial configurations. Sadly, we are just short of $65$, which would have proven that $7$ is necessary. However, this also means that any possibility for an algorithm with at most $6$ comparisons is very delicate and can be proven to not exist without much direct computation. While you can do this by hand (with non-negligible amount of pain), it is easy to do it using a computer. Here's a summary:

• The only first comparison which splits into two cases with each having at most $32$ configurations is $C4-C6$ (giving a $30-30$ split). By symmetry, we may assume WLOG that $C4 > C6$.
• The only second comparisons which split into two cases with each having at most $16$ configurations are $C2-C5$ (same as $C2-C6$ by symmetry, both give $16-14$ split with $16$ when $C2 > C5$) and $C5-C6$ (giving a $15-15$ split).
• Show that no third comparison in the case $C2 > C5$ can split into $8-8$. This means that we must choose $C5-C6$ for the second comparison. By symmetry, we may assume WLOG that $C5 > C6$. Similarly show that no third comparison can split into $8-7$. This yields the required contradiction.