11
$\begingroup$

So there's a counterfeit coin variant that I stumbled across and I'm not sure exactly how to solve it.

It goes as follows:

You have eight coins, two of which are counterfeit. One of the two is slightly heavier than normal, the other is slightly lighter. The two counterfeit coins have the same combined weight as two normal coins.

You have a balance. How many weighings are necessary to identify both the heavier and lighter coin?

I can do it in five, but I strongly suspect you can do it in fewer.

EDIT: Solution for five weighings:

Label your coins 1 through 8. Weigh 1 against 2, 3 against 4, 5 against 6, 7 against 8. If we get three balanced scales and one imbalanced scale, we know which two coins are counterfeit. If we get two balanced scales and two imbalanced scales, assume without loss of generality that 1 was heavier than 2 and 3 was heavier than 4. From this we can deduce that either 1 is the heavy counterfeit and 4 is the light counterfeit, or 2 is the light counterfeit and 3 is the heavy counterfeit. Therefore, we weigh 1 against 4. If they are balanced, then 2 is the light counterfeit and 3 is the heavy counterfeit. Otherwise, 1 is heavy and 4 is light.

EDIT: As mentioned by Mees de Vries below, 3 weighings with 3 possible outcomes each can only distinguish between 27 possible scenarios. We have 56 total possible configurations, and so 4 weighings must be optimal if it is possible.

$\endgroup$
  • $\begingroup$ Four is also enough: weigh three against three; then weigh the two unweighed against each other, two from the first set of three against each other, and two from the second set against each other. The results from those weighings always give you enough information. Edit: but I'm not posting this as an answer, but I highly suspect 3 is enough. $\endgroup$ – Mees de Vries Apr 20 '17 at 21:55
  • $\begingroup$ Nope, this won't work. Consider coins 12345678, with 1 and 3 as the light and heavy counterfeits respectively. 123 get weighed against 456 with 78 aside. This leads to a balanced scale. You weigh 7 against 8 and fine they are both legit. You weight 4 against 5 and find that they are both legit, and therefore so is 6. You weight 1 against 2 and whups, you find that 1 is lighter than 2. You don't know if 2 is the heavy counterfeit or not, or if 1 is the light counterfeit or not. You just know that one or the other (or both) is true. $\endgroup$ – junkmail Apr 20 '17 at 21:59
  • $\begingroup$ You're right, my mistake. $\endgroup$ – Mees de Vries Apr 20 '17 at 22:05
  • 1
    $\begingroup$ But, wait, you can fix that by weighing 7/8 last. Then if you find out that 1 < 2, you don't need to weigh 7 against 8, because you know that they weigh an equal amount, so you can use that fourth weighing to figure out whether 1 is light or 2 is heavy (say, by weighing against 7). $\endgroup$ – Mees de Vries Apr 20 '17 at 22:25
  • 2
    $\begingroup$ Ah. My bad. So don't weigh 5 against 7, weigh 6 against 7 instead. Also, this is optimal, three weighings can't suffice: with 3 possible outcomes, that only distinguishes between $3^3 = 27$ scenarios, and we need to distinguish between 56. $\endgroup$ – Mees de Vries Apr 20 '17 at 22:34
2
$\begingroup$

Yes, 4 weightings is possible. Even more, this is still true even if it is not known whether the combined weights of the 2 counterfeits is heavier, lighter, or same as that of 2 normal coins


Notation

First, let's introduce some notation.

Coins are labelled 1 through 8. H, L, and n denotes the heavy counterfeit, the light counterfeit, and a normal coin, respectively.

Weightings are denoted, for instance, 12-34 for weighting coins 1 and 2 against 3 and 4. The result is denoted 12>34, 12=34, or 12<34 if 12 is heavier, weights the same as, and lighter than 34, respectively.

1234:H means H is among coins 1, 2, 3, and 4. Similarly, 1234:L means L is among coins 1, 2, 3, and 4.

Due to the highly symmetric nature of the problem. A lot of without-loss-of-generality assumptions will be made. As such, they will not be called out.


Algorithm

Begin by 12-34 and 56-78.


Case 1: Double unbalanced (12>34, 56>78)

In this case, we know that either 12:H, 78:L or 56:H, 34:L. Do 13-57 next.

If 13>57 , then either 1:H, 7:L or 1:H, 8:L or 2:H, 7:L. These can be distinguished by 28-nn.

If 13=57, then a simple 2-8 to distinguish 2:H, 8:L and 6:H, 4:L


Case 2: Balanced-unbalanced (12>34, 56=78)

In this case, we know that 12:H and/or 34:L. Do 1-2 next.

If 1>2, then 1:H, 234:L. A simple 2-3 resolves that.

If 1=2, then either 3:H, 4:L or 4:H, 3;L. So 3-4.


Case 3: Double balanced (12=34, 56=78)

This means both H and L is within the same pair. Do 135-246.

If 135>246, then either 1:H, 2:L, 3:H, 4:L, or 5:H, 6:L. Do 1-3 to distinguish.

If 135=246, then either 7:H, 8:L or 8:H, 7:L. Do 7-8 to distinguish.

$\endgroup$
0
$\begingroup$

If you have six coins, I think it takes at least four weighings. (The implication being that it will take more weighings if you have 8 coins.)

Weigh three against three. If balanced, both counterfeits are on one side. Weigh two from one side. If balanced, those are the good coins; otherwise one or both of the coins is counterfeit. From here, it takes at most two more weighings to determine which coin is which.

Weighing two against two at the start is suboptimal. If unbalanced, it tells you at least one of the four is counterfeit; it could be both counterfeits are on opposite sides. Weighing the other two tells you whether the first weighing had one or two counterfeits. If only one was counterfeit, then you spend another weighing figuring out which side had the counterfeit, then need two more to smoke out the counterfeit coins.

Lastly, if you weigh one pair at the start, if unbalanced, then you have either one or two counterfeits there. Weigh another pair. If balanced, then those are known good coins but then you may go through three more weighings to smoke out the counterfeit coins because you have to test both coins on the first weighing against a known good coin. If only one is counterfeit, then you don't know which in the unweighed pair is the other counterfeit.

$\endgroup$
  • $\begingroup$ This does not constitute a proof that it is impossible to solve it for 4 weighings and 8 coins. $\endgroup$ – junkmail Apr 21 '17 at 20:19
  • $\begingroup$ I didn't make that claim, but maybe you can extend it so that it does. $\endgroup$ – John Apr 21 '17 at 21:09

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.