Counterfeit Coin Problem Variant - Two Counterfeits
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.