Breaking Balance (Part C)

Question

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 1

@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

Answer 2

We can

distinguish between $7^3 = 343$ possible outcomes after $3$ weighings.

Now the question is

if you have $N$ coins with $2$ counterfeit ones, how big can $N$ be, such that the number of possible configurations is not greater than $343$?
The number of possible configurations of the coins is $\frac{2 \cdot N \cdot (N-1)}{2} = N(N-1)$.

• The first factor of $2$ is because the coins can be lighter or heavier.
• The second factor of $N$ are the possibilities for the first counterfeit.
• So that for the second counterfeit there are $N-1$ possibilities.
• The division by $2$ is because the two counterfeit coins are indistinguishable.

This means

we have to find the largest integer $N$ with $N(N-1) \le 343$, which yields $N = 19$.

Of course,

this doesn't yet tell you how to use the balance. I fear that in the optimal strategy one has to adapt the weighings on the results of the previous weighings, so that the description will be a rapidly escalating tree of possibilities. Given that you said it took you weeks, I will probably come up with a concrete strategy by next year. 😃

Further requirements of the strategy

are that it only performs measurements where the full 7 possiblities come out with almost equal probability. From the number of possible coin configurations ($342$) and the number of possible outcomes from 3 weighings ($343$) it is clear that we can't afford making a measurement with only 6 possible outcomes.
But why is it purposeful to ensure that all outcomes are equally likely? From an information-theory point of view the information content of the coin configuration is $-\log_2 \frac{1}{342} \approx 8.41785 \, \text{bit}$, while a measurement with all 7 outcomes being exactly equally likely reveals $-\log_2 \frac{1}{7} \approx 2.80735 \, \text{bit}$. The information gain decreases if (conditioned on what we already know from previous measurements) the outcome probabilities differ from $\frac{1}{7}$. At the same time we are only allowed to lose $0.00421225 \, \text{bit}$ along the way, so I'm beginning to doubt that we can actually reach $N = 19$.

To be able

to get 7 different possible outcomes one needs to put the same number of coins into each pan. Let's see how many are optimal:

• For $1$ coin on each pan the most likely result is A = B = C which happens in $240$ of the $342$ cases. Results of the type A > B = C show up in $17$ of $342$ cases each, as well as results like A < B = C.
  Unfortunately this measurement only reveals $1.65009 \, \text{bit}$ on average.
• For $2$ coins on each pan A = B = C happens in $156$ cases, while the A ≷ B = C cases happen $31$ times.
  Here the average information gain is $2.4003 \, \text{bit}$.
• For $3$ coins on each pan A = B = C happens in $90$ cases, while the A ≷ B = C cases happen $42$ times.
  Here the average information gain is $2.73618 \, \text{bit}$.
• For $4$ coins on each pan A = B = C happens in $42$ cases, while the A ≷ B = C cases happen $50$ times.
  Here the average information gain is $2.80489 \, \text{bit}$.
• For $5$ coins on each pan A = B = C happens in $12$ cases, while the A ≷ B = C cases happen $55$ times.
  Here the average information gain is $2.71356 \, \text{bit}$.
• For $6$ coins on each pan A = B = C doesn't happen anymore because there must be at least one counterfeit coin on the scale, while the A ≷ B = C cases happen $57$ times.
  Here the average information gain is $2.58496 \, \text{bit}$.

So the case of $4$ coins in each pan yields the most inforamtion, which would be enough if we could proceed with a more equal splitting of probabilities into the 7 outcomes. But looking at the number of possible realizations for each outcome after the first weighing, we see that for the A ≷ B = C cases we would have to distinguish between $50$ different cases with only 2 weighings, which is impossible.
Hence our upper bound for the number of possible coins is lowered to $N = 18$.

Going

through the same calculations as before, we see that with $18$ coins there are only $306$ different configurations, which is an information content of $8.25739 \, \text{bit}$. With the same argumentation as above, we have to put an equal number of coins in each pan. Let's go through the cases again:

• $1$ coin in each pan:
  A = B = C: $210$ cases
  A ≷ B = C: $16$ cases each
  Information revealed: $1.7084 \, \text{bit}$
• $2$ coins in each pan:
  A = B = C: $132$ cases
  A ≷ B = C: $29$ cases each
  Information revealed: $2.45625 \, \text{bit}$
• $3$ coins in each pan:
  A = B = C: $72$ cases
  A ≷ B = C: $39$ cases each
  Information revealed: $2.76386 \, \text{bit}$
• $4$ coins in each pan:
  A = B = C: $30$ cases
  A ≷ B = C: $46$ cases each
  Information revealed: $2.79428 \, \text{bit}$
• $5$ coins in each pan:
  A = B = C: $6$ cases
  A ≷ B = C: $50$ cases each
  Information revealed: $2.67351 \, \text{bit}$
• $6$ coins in each pan:
  A = B = C: $0$ cases
  A ≷ B = C: $51$ cases each
  Information revealed: $2.58496 \, \text{bit}$

The information gain is greatest for $4$ coins on each pan in the first weighing. In fact, this is the only first weighing in which none of the possible 7 outcomes has to distinguish between more than $7^2 = 49$ cases.
This means we know that the first step must be weighing $4$ coins in each pan.

We can continue

in the case of A = B = C easily, because then we know that the two counterfeit coins are among the 6 which weren't on the balance yet. The solution to this has been given by Brandon_J.

The big mess

happens for the case A ≷ B = C, because we have $46$ cases to distinguish and we must make use of the previously obtained information. To simplify our life we can make use of the symmetry of the problem: If we have a solution for A ≷ B = C, it can be generalized by swapping A, B and C. Furthermore, if we have a solution for A > B = C one can use the same strategy for A < B = C by just swapping the words lighter and heavier.

Answer 3

@ppgdev has gotten the right answer, but whether every detail was properly paid attention to... I don't know. There's a lot to unpack. I've had far more time on this problem, so allow me to explain it as well, and hopefully we can get more people to follow along. I'll be happy to explain anything in more detail, but keep in mind I did all of this months ago and probably forgot some details.

The right perspective to have in order to get the most out of this balance is to think of all the combinations the counterfeits can have for the "solution". Coins #7 and #9 are heavy... Coins #3 and #11 are light... there will be many of them. When you use the balance, it is going to eliminate some of these combinations from what is still possible. If I set up a bunch of coins on the balance and I see pan A go down, any combination that says pan A contains a light coin must no longer be possible. Happily, every time we use the balance it actually removes a bunch of the possible solutions.

So think of it like this: When you arrange coins on the balance it's the same as taking your "solution combinations" and putting them into seven piles, each pile corresponding to an outcome. When you read the actual outcome of the balance, you are able to say that one of the seven piles is still possible, and the other 6 piles are impossible. That's why @A. P. claimed you have 343 maximum configurations, because one weighing could divide that into 7 piles of 49. A second weighing could divide each of the piles of 49 into piles of 7. The third weighing could divide each of the piles of 7 into a pile of 1, representing that you have found a single solution to the puzzle after three weighings.

But, of course, that number assumes you can divide the combinations into seven equal piles. As it turns out, on your first weighing, the six imbalanced outcomes are always equal but that balanced case (typically) is a different number.

When we try to solve the 19 coin puzzle, there is no way to make a first weighing that makes piles of 49 or less. How do you know what piles are what sizes? I'm not getting into it here but there's equations for it. I did it by hand for small numbers of coins and worked my way up until I saw the patterns.

So next up is the 18 coin case. This one is going to fail at the second weighing, not being able to make piles of 7 or less. @ppgdev claims to have found a counterexample to this statement which probably means I have forgotten something. Maybe the correct statement was that there's basically one way to make piles 7 or less but we can exclude it because it fails for a different reason? This was the part of the problem that made me say I don't quite have a "proof" for the answer. I also used a computer program to sweep this area and make sure I didn't miss anything. The me from 4 months ago was convinced 18 coins couldn't work, for whatever that's worth.

The 17 coin case is possible, so let's focus on that.



4 coins per pan gives us the least maximum combinations in any given outcome. You may not know that an adaptive strategy works better than a preplanned one, but I assure you after a few weeks on this problem you'll agree with me. Even though that's true, the information we get in the first weighing isn't enough to make any clever adaptive strategy in our second weighing. It turns out we just want to do the same thing again (4 coins per pan), just making sure to jumble up the coin's positions. Remember, we want to divide the combinations up again, and keeping coins together will only hurt us in that regard. Here's my notation for the first two weighings:


There are 49 different ways this arrangement could go, but luckily most of the cases boil down to the same thing. I get 3 scenarios that effectively cover the 49 cases.

The first case is where one or both of the weighings balanced. It should not surprise you to find out this is solvable, since someone already solved something harder. The other two cases I call the "agree scenario" and the "disagree scenario." One pan went down in each weighing? That's the agree scenario. One pan went up in the first but one pan went down in the second? That's the disagree scenario.




So you can follow along with my logic in the picture, I did my best to label my process. We want to identify, specifically, which of the solutions still remain possible, and then build our 3rd weighing to address them. I did this so many times by hand that I was doing them in my dreams. Anyway, the hardest of the scenarios has to be the agree scenario. It has 7 solutions remaining and we have to build our 3rd weighing to place one solution along each of the 7 balance outcomes. From experience, I know this isn't always possible. This one happens to be possible, but understanding this probably counts as the second-hardest part of this whole question. For a number of days I was convinced that the answer to this question was 16 coins because of this exact spot. See the pictures for a rough gist of how I go about it, it boils down to trial and error. Lastly I phrased a plan to build a 3rd weighing such that it actually covered the entire scenario. Hopefully you can follow along with my lingo. "Twice-light" means a coin was on a pan that went up in both weighings... that sort of thing.

So that's everything. I know this isn't everyone's cup of tea and I'm sorry if you dislike puzzles of this... level of complexity. There's some cute ideas in there but even with my explanation the only correct description for this is that it's a "big mess."

Oh yeah, the variants that are much worse:

Solve for three identical counterfeit coins instead. This one requires computer aid, as far as I'm concerned. Instead of 7 balance outcomes we now have 13, and that makes the whole thing a nightmare... that was already inside another nightmare.

Solve using a preplanned weighing scheme. I thought I had the right answer until a computer search showed me I could do one coin better. Even after seeing it I can't explain why it works. (Also... don't combine these two variants. You're welcome.)

Answer 4

Assuming there is no other info we can infer from previous weighing (all balanced/eliminated) then you need to check all remaining coins. We can have at most three unknown coins for last weighing.

Set aside one unknown and compare the other two to reference coin.

1. if both tip against reference then both outliers are on the scale.
2. if one equals reference coin then the other coin on scale and the one set aside are the outliers

Now the problem with having two outliers is that they could be separate or together on the arms of the scale. And we also can't infer from how the scale tips since the outliers could be light or heavy. And if we set aside coins, then its possible for one to be there or only one outlier on the scale.

This prevents us from eliminating coins on first weighing if the scale does not balance, and we need a reference coin for our second or last compare. This means that we can only load three coins on the first weighing with the rest set aside. [as discussed in comments, possible to have 6 in first weighing, but still 4 unknown in second weighing making total coins 6+4 = 10)

If they all match then we have our reference coins (all three of them), and outliers are in the unchecked coins (no other info can be inferred)

-- But we can't just put all unchecked coins on scale for second weighing, we can't infer anything from that (could be separate/together, or light/heavy). So reference coins need to be used in second weighing, question is how many that will still give us manageable number of unknowns for last weighing.

-- If one arm will be the same as reference then third arm has both outliers, thus second weighing could have tested six unknowns (3 each) and we only need to test three unknowns in the third arm. As mentioned at the beginning this is doable.

-- BUT if other two arms of scale tip the same against reference then outliers are in each arm, and we will need to test both sets (worst case scenario) to identify the outliers in each.

----- This means we can actually test only up to four unknowns (two on each arm) and not six in second weighing. We also need to take note if arms with outliers are lighter/heavier compared to reference.

----- So for last compare set aside one unknown and place three unknown on scale.
-------- If we were looking for lighter outliers then if two arms go up those are the light outliers, if only one arm goes up then other outlier is the coin we set aside. Same logic if looking for heavy outliers. Note that we were able to infer from last weighing without using reference coin because we observed how the scale tipped as additional info.

So far that sequence of comparison allows for 3 unknowns from first compare plus 4 unknowns in second compare (total 7). Last compare just isolates the outliers.

What if first three coins did not match? Then we don't have our reference coin/s and we either have one or two outliers on scale. We don't know for certain because outlier could be lighter or heavier.

-- We can check the two that went up/down (they are of same weight) against two other pair of unknowns, the third coin from first compare is set aside.

----- If the two coins that previously went up still stays up, then both are the light outliers. No need to do third compare. Same logic for heavy outlier (went down) scenario.

----- Remember that both coins are of same weight (result of first compare), so the other scenario is one outlier is in the four unknown just placed (two on each arm) and the other outlier is the coin we set aside.
----- So one of these arms will go up/down same as the coin we set aside earlier, giving us two unknowns to check. Last compare is then to determine which of the two has same weight as the coin we set aside earlier.

This sequence of comparison also allows for 3 + 4 = 7 coins total. It might be possible to solve using more coins (three on each arm) since other logic path has first weighing balanced, and we only have two unknowns in final compare (we can have up to three unknowns for last weighing). But this explanation is already too long. Might do follow-up if I have time to analyze 3 + 7 = 10 coin scenario.

But definitely if the problem had stated that there is only one outlier coin, or its specified that outlier is lighter/heavier, or this uses a 2 arm balance (seesaw) then you could have tested more than 7.