mathematics - Breaking Balance (Part C)

For a starting number of otherwise identical coins there are among them TWO IDENTICAL counterfeit coins which are either heavier or lighter than the rest. Using a three-pan balance (described in detail below), and three weighings, what is the most number of starting coins (including the counterfeits) you can have while being able to always determine the counterfeits and whether they are both heavier or both lighter?

This should not be confused with the balance detailed in Find 2 heavy coins among 27 with a 3-pan balance as it has a bunch of different rules.

So there isn't confusion, I want to explicitly state how this thing works. It has three equal-length arms supporting three pans (120deg apart), and is balancing on a point. It works like other balances in that the center-of-gravity is below the balance point and thus will tilt to counteract imbalance in the pans.

There are exactly 7 outcomes the balance will give you. The first is the "balanced" outcome, where all pans stay at the same height. The other six are variations on the following:

One "lone" pan will go up or down, and the other two pans will be equal to each other but move opposite the lone pan. Given that there are TWO IDENTICAL counterfeit coins, this may be less informative than you might otherwise hope for. My shorthand for the 7 outcomes is as follows:

• A = B = C



• A > B = C


• A < B = C


• B > A = C


• B < A = C


• C > A = B


• C < A = B

For sake of convention, I consider the coins to be numbered 1 through whatever, and the pans labeled A, B and C. The 4th location, D, is used to denote a coin not being the scale.

Warning: I do not believe there is a "cute" solution and it took me weeks to solve it... and even then it isn't quite a "proof". I really enjoyed going through it, but seriously... this isn't for everybody. And for those that do get it... there's a bunch of much harder variants awaiting you!

Answer

@A.P. Provided a great analysis! I am picking up from were he/she stopped:

Given $18$ coins, I found (with the help from my computer :-) a second weighing that would split potential counterfeit coins into 7 different groups with each having either 7 or 6 potential counterfeit pairs. I thought the problem is solved, but unfortunately some of the groups with 6 coins were impossible to crack with just one remaining weighing. My findings are described bellow. Using this second weighing that I found, I also show how to solve the problem with total $17$ coins.

So $17$ coins is the best total number of coins when I could still find counterfeits and their type with just 3 weighings. I do not know if it is doable with $18$ - it might be. At some point I will modify my program to do the exhaustive search :-)

Reasoning:

As @A.P. pointed out, we have to only analyze the case $A > B = C$ with 4 coins on each pan. We will number the coins from 1 to 18. We will use notation $AN$ to refer to the content of pan in weighing $N$. In the analysys of the results weighing $N$ we will use scenario $XN$ if a counterfeit coin is heavier than normal and $YN$ if a counterfeit coin is lighter. Let's (following @A.P.) make the first weighing:

$A1:$ 1, 2, 3, 4;
$B1:$ 5, 6, 7, 8;
$C1:$ 9, 10, 11, 12;
$D1:$ 13, 14, 15, 16, 17, 18;

We have 2 possible scenarios for the distribution of counterfeit coins:

$X1:$ Heavy case: at least one is in $A1$, the other is in $A1$ or $D1$;

$Y1:$ Light case: $B1$ has one and $C1$ has one.

Let's proceed with weighing #2 in the following way

$A2:$ 1, 5, 13;
$B2:$ 2, 6, 14;
$C2:$ 3, 7, 15;
$D2:$ 4, 8, 9, 10, 11, 12, 16, 17, 18;

Let's look at the 7 cases one by one.

Case 1, $A2 = B2 = C2:$
$X2:$ 4 and one of 16, 17, 18;
$Y2:$ 8 and one of 9, 10, 11, 12;
Weighing #3:
$A3:$ 9, 16
$B3:$ 10, 17
$C3:$ 11, 18

We have at most one counterfeit coin on the scale. If only one pan is down, we have a heavy case and the down pan uniquely determines the second heavy coin. If only one pan is up we have a light case and the up pan uniquely defines the second light coin. If $A3 = B3 = C3$ then coins 8, 12 are light counterfeits.

Case 2, $A2 < B2 = C2:$
$X2:$ counterfeit is one of the pairs {2, 3} {2, 15}, {3, 14}
$Y2:$ 5 and one of 9, 10, 11, 12;
Weighing #3:
$A3:$ 9, 1
$B3:$ 10, 14
$C3:$ 11, 15
Notice that again - we have at most one counterfeit coin on the scale and potentially lighter coin is paired with a potentially heavier coin. This solved in the same way as case 1. If $A3 = B3 = C3$ then coins {2, 3} are heavy counterfeits.

Case 3, $A2 > B2 = C2:$
$X2:$ counterfeit is one of: {1, 13} {1, 16} {1, 17} {1, 18} {1, 4} {4, 13}
$Y2:$ impossible, we know that counterfeit coins are heavy

I was not able to find one weighing to deferenciate all 6 cases. But if we were dealing with only 17 coins (no coin #18), the following weighing #3 would solve this case:

$A3:$ 2, 4
$B3:$ 3, 13
$C3:$ 5, 6

$A3 = B3 = C3$ ==> $X3:$ {1, 17}
$A3 > B3 = C3$ ==> $X3:$ {1, 4}
$B3 > A3 = C3$ ==> $X3:$ {1, 13}
$C3 > A3 = B3$ ==> $X3:$ {1, 16}
$C3 < A3 = B3$ ==> $X3:$ {4, 13}

Case 4, $B2 < A2 = C2:$
$X2:$ counterfeit is one of: {1, 15} {1, 3} {3, 13}
$Y2:$ counterfeit is 6 and one of the 9, 10, 11, 12

This can be solved the same way as case 2.

Case 5, $B2 > A2 = C2:$
$X2:$ counterfeit is one of: {2, 14} {2, 16} {2, 17} {2, 18} {2, 4} {4, 14}

$Y2:$ impossible, we know that counterfeit coins are heavy

The same as case 3 - could not solve in one weighing, but can be solved by dropping coin 18

Case 6, $C2 < A2 = B2:$
$X2:$ counterfeit is one of: {1, 14} {1, 2} {2, 13}
$Y2:$ counterfeit is 7 and one of the 9, 10, 11, 12
This can be solved the same way as case 2.

Case 7, $C2 > A2 = B2:$
$X2:$ counterfeit is one of: {3, 15} {3, 16} {3, 17} {3, 18} {3, 4} {4, 15}
$Y2:$ impossible, we know that counterfeit coins are heavy

The same as case 3 - could not solve in one weighing, but can be solved by dropping coin 18