[Math] Counterfeit Coin Problem Variant – Two Counterfeits

discrete mathematicsrecreational-mathematics

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.

Best Answer

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.

Related Solutions

[Math] Counterfeit Coin Problem – 8 Coins

Let your first weighing be ABC vs DEF. If it's balanced, then you know that the fake is either G or H, and that can be checked with a single weighing, for instance G vs A.

If the first weighing was unbalanced, next weigh AD vs BE. This can go one of three ways:

It's balanced. That means that either C or F is counterfeit, which can be checked with a single weighing.
It goes the same way as before (i.e. ABC and AD were both the heaviest, or they were both the lightest). In that case, the counterfeit coin stayed in its dish, which means it's either A or E. Do a single weighing to decide which one of them is counterfeit.
If it went the opposite way of the first weighing (i.e. ABC was heaviest and AD was lightest or the other way around), that means that the counterfeit coin changed sides, which means it's either B or D. Either way, you only need one more weighing to figure out which one it is.

This method can actually be expanded all the way up to $12$ coins, following roughly the same procedure, and still managing in only $3$ weighings. (Note that none of the final weighings are with only two candidate counterfeits, when you can easily handle $3$, and in the case where the first weighing is balanced, you only need two total weighings. That leaves a lot of room for a bigger pool of coins, and that limit happens to be at $12$.)

Difficult coin weighing puzzle: 14 coins, 1 fake (heavier or lighter), 3 pre-determined weighings

Suppose a triple of weighing results determines a coin. If a weighing result is "equal" then the coin did not appear in that weighing. Otherwise, the coin appeared on either the "less" side of each weighing or the "greater" side of each weighing depending on whether the coin was lighter or heavier.

For each coin, then, choose a distinct weighing result pattern that will determine that coin. (Weighing result patterns that are completely flipped must identify the same coin with the opposite weight, so we won't use these.)

A < = =
B = < =
C = = <
D < < =
E < = <
F = < <
G < > =
H < = >
I = < >
J < < <
K < < >
L < > <
M > < <
N = = =

Then we know exactly how to assemble each weighing (ie A appears in the first weighing only; G appears on opposite sides of the first two weighings; J appears on the same side of all weighings; etc) except that we don't know which side to put the coins on, but deciding the sides turns out to be easy, as we merely need to balance the number of coins in each weighing. Coin X (the known good coin) is needed because there are otherwise nine coins involved in each weighing. We will not be able to distinguish between coin N being lighter or heavier.

One solution is

AGJKL-DEHMX
BIJKM-DFGLX
CHJLM-EFIKX