Beam Balance Strikes Back

Consider coins A, B, C, D, E, F. Knowing which coin is second-lightest inherently requires that you know which coin is the lightest (this isn't immediately obvious but easy to convince yourself). As shown in the sample problem, this requires at least five moves: make three comparisons and form winners and losers piles, let's say A>B, C>D, E>F, then make two comparisons within the losers pile, let's say B>F and D>F, showing F is the lightest. Then the second-lightest must be one of B, D, or E; two more comparisons will reveal the answer.

Let the six coins be $A,B,C,D,E,F$ , and start by weighing $A\,v\,D$ , $B\,v\,E$ and $C\,v\,F$ . Suppose that $A < D$ , $B < E$ and $C < F$ . The second lightest coin is either the middle coin of $A,B,C$ or else the coin originally weighed against the lightest coin of $A,B,C$ (in other words, if $A < B < C$ , the second lightest coin could be $D$ ). We can determine the order of $A,B,C$ in three weighings - suppose that $A < B < C$ . One more weighing of $B \,v\,D$ tells us whether $B$ or $D$ is the second lightest coin. We can determine the second lightest coin in $\boxed{7}$ weighings.

Since we do not know the weights of the various coins, there is no advantage to be gained by comparing the weights of groups of coins, so we must always simply compare one coin with another. For any algorithm, let us see where we have got to after the first three weighings.

• If the first three weighings involve only three coins, we must have compared each of these three coins against the other two. We will know the rank order of these coins ( $A < B < C$ , say), but will know nothing about the other three coins $D,E,F$ . The second lightest coin could be any of $A,B,D,E,F$ . If it was the case that all three of $D,E,F$ were less than $A$ , it would take three weighings to determine the middle coin of $D,E,F$ , plus at least one weighing to establish that all of $D,E,F$ were less than $A$ . It would take at least $7$ weighings to solve the problem.
• If the first three weighings involve four coins, testing $A \,v\, B$ , $A \,v\,C$ and $A\,v\,D$ , we might obtain that $B,C,D < A$ . Thus any one of $B,C,D,E,F$ could be the second lightest, and it will take four or more weighings to decide which it is. It will take at least $7$ weighings to solve the problem.
• If the first three weighings involve four coins, testing $A \,v\,B$ , $C\,v\,D$ and $A\,v\,C$ , we might obtain that $B,C < A$ and $C < D$ .Thus any one of $B,C,E,F$ could be the second lightest (and, indeed, $D$ could be the second lightest if $C$ is the lightest). Since we have obtained no information so far about the relative weights of $B,C,E,F$ , it will take at least $4$ more weighings to sort this out, and so we will need at least $7$ weighings to solve the problem.
• If the first three weighings involve five coins then, without loss of generality, they test $A\,v\,B$ , $A \,v\,C$ and $D \,v\,E$ . We might obtain that $B,C <A$ and $D < E$ . in which case any one of $B,C,D,E,F$ could be the second lightest. If $B,C,F$ were the three lightest, it would take $3$ weighings to determine the middle coin of the three, and at least one more weighing to ascertain that $D$ and $E$ were not involved. We would need at least $7$ weighings to solve the problem.
• If the first three weighings involve all three coins, the first paragraph explains how $7$ weighings are not just necessary but also sufficient.

6 coins are A, B, C, D, E, and F.

Divide them into 2 groups: A, B, C / D, E, F.

Compare A and B, then compare heavier one between the 2 and C. The heaviest coin be expelled, and I've made 2 tries.

Do the same work with D, E, and F. Now, Here are 4 coins left, with 4 tries in total.

Now, compare 3 coins out of 4. with 2 tries, I may expel the heaviest coin. And since I know the relative weight of lighter 2 coins, now compare the heavier one of the two and F. Finally, expel the heavier one.

I have 2 lightest coins, knowing which is heavier. And therefore total tries are $2 \times 2 + 2 + 1 = 7$ .

If we designate the minimum value of $M$ , for $x \ge 2$ coins, as $m(x)$ , then for any integer $y \le x$ ,

$m(x+y)\le m(x)+y+1$

(which establishes the bound that Ivan Koswara already gave, $m(x) \le x+\lceil \log_2 x \rceil -2$ , and in particular $m(6)\le 7$ , but I have not found a way to prove minimality).

$Proof.$

Step (1): Test any $y$ distinct pairs of coins, and set aside the heavier coin from each test.

Step (2): Take the $x$ coins that have not been set aside, and perform the appropriate $m(x)$ tests to determine which out of those coins is the lightest and which is the second lightest, and designate them as CoinA and CoinB respectively.

Step (3): CoinA is the lightest out of all $x+y$ coins, and the second lightest must be either CoinB or the coin (if there was one) that was tested against CoinA in Step (1), so testing these two coins against each other completes the task.