9
$\begingroup$

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?

enter image description here

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:

enter image description here

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!

$\endgroup$
  • $\begingroup$ A balance like this one but with 12 plates would also work for your problem A :) $\endgroup$ – J. Dionisio Jan 26 at 17:48
  • $\begingroup$ @J.Dionisio If the 12 plates were equally spaced you couldn't tell whether one coin is lighter than the rest or if it's the one on the opposite side which is heavier. $\endgroup$ – A. P. Jan 26 at 17:54
  • $\begingroup$ @A.P. you're right, I didn't think of that! $\endgroup$ – J. Dionisio Jan 26 at 18:10
  • $\begingroup$ Suppose I placed a lighter counterfeit coin into pan A, a normal coin into pan B, and a heavier counterfeit coin into pan C (still only two counterfeit coins), would all three pans be at different heights? $\endgroup$ – ZanyG Jan 27 at 3:32
  • $\begingroup$ @ZanyG It certainly would but that's not possible in this puzzle since the counterfeits are identical. $\endgroup$ – Dark Thunder Jan 27 at 3:56
2
+100
$\begingroup$

@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

$\endgroup$
  • $\begingroup$ You got it. It's a little hard to tell if you thought of everything, but I'll give you the benefit of the doubt. I still you owe you on my student council question. Anyway, I've posted my explanation as well, so maybe between the two of us we can convince a third person that this wasn't a completely absurd problem. Just mostly absurd. Congrats! $\endgroup$ – Dark Thunder May 25 at 20:17
  • $\begingroup$ FYI it isn't possible with 18, at least not if my own program is correct. $\endgroup$ – Gareth McCaughan May 25 at 21:15
  • $\begingroup$ Dark Thunder, thanks. Actually @A.P. deserves the bonus for his/her great insight! The strangest thing about 18 coins case is that when the second weighing splits 46 potential counterfeit pairs into 4 groups of 7 and 3 groups of 6, it is the groups of 6 that are unsolvable, and groups of 7 are easy. More over, for the groups of 6 we already know that counterfeits are heavier - very counter intuitive! I guess it is harder to find different weighing scenarios with one type of counterfeits. Turns out a second weighing creating groups that would contain both heavy and light pairs does not exist. $\endgroup$ – ppgdev May 25 at 22:20
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, take heart. If you have that upper limit figured out after an hour you're going a lot faster than I had. $\endgroup$ – Dark Thunder Jan 26 at 20:45
  • $\begingroup$ Hey, I forgot that I answered that question XD. Thanks for reminding me - that was a fun puzzle. Also - have an upvote for some excellent work. $\endgroup$ – Brandon_J May 23 at 15:02
2
$\begingroup$

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

enter image description here

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:

enter image description here
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.

enter image description here
enter image description here enter image description here

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Welcome to puzzling SE! For future reference it is common here to add spoiler markers ( >! ) to hide info crucial to the solving of the puzzle so others can try too, although may not be necessary for a long answer such as this. Also try to avoid spam editing and make sure to look over the whole post and make all edits at once when possible. $\endgroup$ – gabbo1092 May 23 at 15:14
  • $\begingroup$ Yes, welcome to the wild world of wishing the "spoiler markers" were more intuitive to use. As for your answer, I think you're limiting yourself in your opening statement. There's a lot more you can know from a weighing than just that maybe you can eliminate some neutral coins. A single weighing has 7 outcomes and you can use all of them to your advantage, typically. $\endgroup$ – Dark Thunder May 23 at 16:09
  • $\begingroup$ Gave more thought after meal. Ten is doable, 6+4. If 6 balanced in 1st load then 4 unknown doable as shown. If not then confirm odd arm if it has 1 or 2 heavy/light. Say it went down, swap out coins in other arms. If it stays down then has 2 heavy. If 2 arms went down then heavy in each. 4 unknown from 2 arms with tipping info doable. It wont go up since light would be in the 4 we swapped out from arms that went up in 1st compare. Again 4 coins known to have 2 light outlier doable. More than 6 unbalanced will have too many unknowns, doesnt eliminate hence need for.confirmation step. $\endgroup$ – delisyoso31 May 23 at 16:53
  • $\begingroup$ My thought process was along the lines of 2 equations to solve 1 unknown, 3 equations for 2 unknown in algebra. Sorry cant see how counting combinations/permutations helps with the process of elimination. $\endgroup$ – delisyoso31 May 23 at 16:58
  • $\begingroup$ There was another question asked by user A. P. that was identical to this one but instead asked about using two weighings total instead of three. You are claiming that at most 4 unknown coins can be solved in two weighings but that's not what he found. You may want to look there. $\endgroup$ – Dark Thunder May 23 at 19:27

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.