Here's an algorithm that requires maximum 7 measurements (I believe):
Let's first set some terminology, note that each measurement of n coins can be one of 4 cases:
- Case 0: All standard coins M = n.s
- Case X: Contains one fake coin: M = n.s + x
- Case Y: Contains other fake coin: M = n.s + y
- Case XY: Contains both fake coins: M = n.s + x + y
Obviously you don't know upfront which case a measurement is, and if x=y then you can't distinguish cases X and Y, and if x=-y (canceling out) then you can't distinguish cases 0 and XY.
With that out of the way, here's how the algorithm starts:
The first 4 measurements are as follows:
Note that:
- All four measurements are different in size (11,12,13 and 14 coins)
- Together, they divide the 24 coins in the 16 parts: 8 pairs and 8 individual coins
- One coin is not measured
Example:
Suppose the measurements are as follows: M1=110g, M2=119g, M3=132g, M4=141g.
If we knew upfront which case each measurement was (eg. 0,X,Y,XY), then we knew which parts the fake coins are in:
And with one or two extra measurements, we would have located the fake coins.
We would also be able to solve the linear equations:
- 11s=110
- 12s+x=119
- 13s+y=132
- 14s+x+y=141
And conclude that s=10, x=-1 and y=2.
But we don't know the cases upfront, and there are in fact 128 valid case configurations (8 where the fake coins are in the same part, and 16*15/2 where they are in different parts).
However, with this particular example, all other 127 configurations would result in a set of equations that don't yield a solution. (Here it really helps that the measurement sizes are different).
To generalize:
After the first 4 measurements, the algorithm considers all 128 valid configurations and tries to solve (128 times) the corresponding set of linear equations. In most cases only one or two configuration will yield a solution, and it should be trivial locating the coins within 3 remaining measurements.
There are some worse case scenarios though:
Scenario 1
If all 4 measurements have the same average coin weight, then this must be s. Furthermore, at least one of these measurements must include fake coins (since there's only 1 coin unmeasured). So the fake coins must cancel out (x=-y) and reside together as one of the 8 pairs.
In our algorithm, that would mean that 120 configurations would fail, and 8 configurations will solve to the same value of s. Each solvable configuration would have one coin solution.
Finding the fake pair among 8 pairs, can be done in 3 measurements using binary search:
Scenario 2
Three measurements have the same average coin weight. Again, this must be s, but now there will 9 solvable configurations. Let's illustrate assuming M3 was the odd measurements. The other 3 divide the coins into 8 'slices'of 2,3 of 4 coins each:
Either the fake coins are all in the top-left slice that is outside of the other 3 measurements (configurations 0,0,X,0 or 0,0,XY,0)
Or the fake coins cancel out and are together in any slice, with only coin X in the deviating measurement. That's another 7 configurations (eg. XY,0,X,0).
By now, we know the values of s and x, so we can construct extra measurements with 3 possible outcomes: 0, X and "other". So three more measurements can distinguish 27 cases, as long as you balance the odds of the 3 outcomes.
The 9 solvable configurations add up to at most 19 possible fake coin combinations (M3 is the worst case), so that's well within reach.
Scenario 3
Suppose all measurements are off by the same offset. The trivial solvable configurations are X,X,X,X and XY,XY,XY,XY, but there's 7 more that are solvable where x=y (eg. X,Y,X,Y).
Again 9 configurations in total, similar to previous case and should be well within reach.
Other bad scenarios?
This is where the 10% uncertainty comes in... I truly believe the cases above are the worst. There could be the odd measurement combination that has an extra solution, but not at the scale of 9 configurations.
Therefor, I strongly believe (but am not certain) that this strategy will always complete within 7 measurements.
