Counterfeit Coin Problem Variant - Two Counterfeits

Question

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.

Answer 1

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.

Answer 2

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.