I have twenty-four identical-looking coins, but two are fake and weigh possibly different from each other, though definitely different from the remaining genuine coins. I have a weighing scale and a two-pan balance.
At most how many times must I use one or the other, or both, to determine the two fake coins?
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:
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
Suppose that 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 (actually the worst case). The other 3 divide the coins into 8 'slices'of 2,3 of 4 coins each:
Either the fake coins are all in the toplight slice (the one that is outside of the other 3 measuremen) (configurations 0,0,X,0 or 0,0,XY,0) Or the fake coins cancel out and are together in any slice, with one in the deviating measurement. That's another 7 configurations (eg. XY,0,X,0, 0,0,X,XY,...).
By now, we know the values of s and x, so we can carefully construct extra measurements with 3 possible outcomes: 0, X and "other". So three more measurements can distinguish 3^3=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, 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, just like the previous case and should therefor 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 are some more sets of 2 or 4 'symmetric' configurations, or the odd set of measurements that by have a false solution, but not at the scale of the scenarios described above, where 9 configurations trigger 19 possible coin combinations.
Therefor, I strongly believe (but am not certain) that this strategy will always complete within 7 measurements.
Mathematical proof (for the balance only):
$n$ weighings can give at most $3^n$ different outcomes.
Letting the number of coins be $c$, there can be $c(c-1)$ different ways the fake coins can be arranged if the fakes are of different weights. If their weights are equal, it's $c(c-1)/2$.
Now let's take a look at their weight:
- If the weights are different, there are three different sub-possibilities: both could be lighter than normal, both could be heavier, or when only one is lighter, the sum could be heavier/lighter/equal than/to two normal coins. That makes $5c(c-1)$. We just need to find the two fakes in no particular order, but even so you can't identify them without differentiating them from each other when their average weight equals a normal coin's, so it's not $7c(c-1)/2$.
- If the weights are equal, they're both lighter or heavier, making $c(c-1)$.
We want the sum, $6c(c-1)=3312$, to not exceed $3^n$, so $n$ must be 8. Even disregarding the average of two fakes, the sum would be $4c(c-1)=2208$ possibilities if they aren't (both heavy, both light, one heavy and one light, with the 1st or 2nd being heavier than the other), and $2208>3^7$.
Steps:
Let's divide the coins into 4 groups of 6 and weigh the first two against each other.
+ If the weights are equal, both fakes must be among either the first two or the last two groups of 6. Then weigh the 1st and 3rd against each other.
++ If we also get a balanced result from that, both fakes must be in the same group (average is normal for 1, 2, 3). Weigh the 4th against the 1st. If one is heavier than the other (++-), the fakes must be in the 4th. Doable. If they're all equal (+++), the average is also normal for the 4th. Then split all of them into two, and weigh the first splits against the other. If the result is balanced (++++), take each from the splits and measure 4 vs 4. After 2 more turns (6th weighing), 2 turns are enough to find out the light and heavy coins. If there's no balance (+++-), the light coin is on the lighter side, and heavy one is on the other. It's now a game of 12 coins with 1 fake we know is light or heavy. Doable again.
+- If we don't get a balanced result after the + stage, the fakes could be distributed like this:
- Two in the 3rd, but they don't average out to a real coin.
- One in the 1st and one in the 2nd, but their weight is equal.
- One in the 3rd and one in the 4th.
Split the 3rd into 2 groups of 3 and measure. If the result is balanced (+-+), only the second possibility is valid, and the first if there are identical fakes on both sides. Compare one of the sides to 3 coins we know are real to rule it out. If the 1st is found to be heavier than the 3rd after +, the fakes must be heavier, and lighter otherwise. We can find them after 4 more weighings (7). If the result isn't balanced (+--), the first and last scenarios are possible. If the 1st is found to be heavier than the 3rd after +, there must be light fake(s) in the 3rd, and the lighter side in the +-- result is more suspicious. If the 1st is lighter, the opposite is the case. Then weigh the 4th against the 1st. If the 4th is heavier, there's a heavy coin in it, or a lighter coin if it's lighter (+---). Now we need 4 more weighings to find out the fakes. If the 1st is just as heavy as the 4th (+--+), both fakes must be in the 3rd. Weigh the "less suspicious" side of the 3rd against three coins we know are normal. If the result isn't balanced, we can succeed in 7 weighings. If it is, we can also win.
If the 1st and 2nd aren't equal (-), and neither are the 1st and 3rd (--), these are the possibilities:
- The fakes are in the 1st, and they don't average out to a normal coin.
- The 1st has no fakes, but the 2nd and 3rd do.
- The 1st has 1 fake. If the 2nd or 3rd has any fake, its weight is different from the one in the 1st.
Split the 1st into 2 groups of 3 and measure. If the result is balanced (--+), the first scenario is possible if there's one of the two identical fakes on each side, and so is the second. Compare one of the sides to three coins from the 4th. An unbalanced result is doable, so let's assume we got a balanced result (--++). Then only the second scenario from -- is possible. It's also doable.
If --- is the case, the first and third scenarios are possible. The 1st group has unbalanced parts, with the heavier side being more "suspicious" (if the 1st is heavier than the next two). If the 1st, 2nd and 3rd groups are guaranteed to have different weights, only the third scenario is possible, and either the 2nd or 3rd group has the other fake. Compare the 4th group to the 2nd. If the result is balanced (---+), the fakes are in the 1st and 3rd, otherwise 1st and 2nd. Doable.
If the 1st, 2nd and 3rd groups aren't guaranteed to have different weights (the 1st is heavier/lighter than both the 2nd and the 3rd), weigh the 2nd against the 3rd. If the result is balanced (---+), only the first scenario is possible, or the 3rd if the fakes are in the 1st and 4th. Test the less suspicious side against one half of the 4th. If the results are balanced (---++), the fakes might be distributed like these:
- One is heavy, one is light, both on the heavy side = 6 (lighter side = normal)
- Both heavy, both on the heavy side = 9 (lighter side = normal)
- One on the heavy side, one in the other half of the 4th.
Weigh the "other half" against 3 normal coins. If the result is balanced, use the remaining 2 turns to find out the fakes in the 1st. If not, 2 turns are still enough.
If the less suspicious/lighter side is heavier than half of the 4th (---+-), the fakes might be distributed like these:
- Both heavy, not equal, both on diff sides = 9 (lighter side = heavy)
- The lighter side is all real, but the half of the 4th is light.
Weigh the first half against 3 normal coins. If the result is balanced, use the remaining 2 turns to find out the fakes in the 1st. If not, 2 turns are still enough. The lighter version is also doable.
Now let's go back to the 4th weighing. If the 2nd and 3rd groups also weigh differently (----), only the third scenario is possible, and the 4th has no fakes. There are the possibilities:
- 1st>2nd>3rd -> 1st has a heavy fake in its heavier half.
- 1st>3rd>2nd -> 1st has a heavy fake in its heavier half.
- 3rd>2nd>1st -> 1st has a light fake in its lighter half.
- 2nd>3rd>1st -> 1st has a light fake in its lighter half.
Find the fake in the 1st with 1 more turn. Then compare the middle group with the 4th. If it's normal, we can deduce the other is in the opposite position of the 1st's. Two is enough. If it's lighter or heavier, it's also doable.
A smaller case:
For $c=5$:
1. Weigh $A$ and $B$ against $C$ and $D$.
- If the weights are equal (+), either one side is all-normal and another consists of heavy and light fakes, or both have one identical fake each. Either way, $E$ is normal, so we can use it to find out the fakes in our next 3 weighings. 4 moves.
- If the weights are different (-), let's say $A+B>C+D$.
2. Weigh $A$ against $B$. If the result is balanced (-+), $A$ and $B$ are both normal or heavy. Then...
3. Weigh $A$ against $E$. A balanced result (-++) means the fakes are $C$ and $D$. 3 moves. If $A<E$ (-+-), weigh $C$ against $D$, and the fakes are $E$ and the lighter one from this measurement. 4 moves. If $A>E$ (-+-), weigh $C$ against $D$. If it's balanced (-+-+), the fakes are $A$ and $B$, and otherwise (-+--) $E$ and the lighter one from this measurement. 4 moves.
2b. The second measurement isn't balanced either (--). Weigh $C$ against $D$. If the results are balanced (--+), they're both real. Then compare the lighter one out of $A$ and $B$ to $C$ or $D$. If the result is balanced (--++), the fakes are the heavier other and $E$, otherwise (--+-) both $A$ and $B$. If the results from $C$ vs. $D$ aren't balanced (---), 2 more weighings are needed to differentiate between $hn-nl-n$, $hn-h^-n-n$ and $nl-nl^--n$. 5 moves, fitting for the formula. If 5 is really the solution, that means $6c(c-1)$ is right.
($h$: heavy, $n$: normal, $l$: light, minus superscript: same state but lighter than the other coin with the same letter).
Balance + weighing scale: TBA
As Pumbaa pointed out, many strategies struggle or fail with the case where the 2 false coins have opposite weight-offsets that can cancel each other out.
Edited: I originally posted a strategy that required 17 moves... but in the meantime, I found a significantly better one: There is a strategy that requires at most...
9 measurements, all using the 2-pan-scale
Here's how it goes:
You divide the 24 coins in 8 stacks of 3 coins. (make sure to mark the coins so that you always know what stack they came from). Then we compare the stacks in 4 pairs. (stack 1 versus stack 2, stack 3 versus stack 4, etc...). Out of these 4 measurements, 0, 1 or 2 can return an inequality (where the scale is not balanced). Let's handle these 3 cases:
Case A: Two of the stack-comparisons were unequal: That means that we can confirm the other 12 coins as genuine and look for one false coin from each unequal measurement. To find a false coin in such a stack-pair, we remove one coin from both stacks, and swap one coin to the other side. The resulting 2x2 coins are compared. This measurement will reveal that the false coin is either among the 2 removed coins, or among the 2 swapped coins or among the 2 other coins. One more measurement (with the help of a genuine coin) will reveal the false coin. If we do that for both stack-pairs, we get a full solution in 8 measurements.
Case B: One measurement is unequal: This means that both false coins must be among the 6 coins of that measurement. Finding them takes 5 measurements: Comparing coin 1 and 2, then coin 2 and 3 etc... (I'll leave it to the reader to work out the details. Hint: At least 1 measurement will return equal, and that every unequal measurements must include at least one false coin). That's a total of 9 measurements
Case C: All measurements return equal, that is only possible in a few special cases where both false coins are part of the same measurement (but we don't know which one). For the 5th measurement, put stacks 1 and 3 on one side and stacks 5 and 7 on the other (so 6 coins on each side).
Case C1: If this 5th measurement returns equal, then both false coins must be in the same stack, canceling each other out with opposite weight offsets. Our 6th measurement: From stacks 1 to 6 put one coin on each side of the scale (so 6 coins on each side):
Case C1a: If the scale returns equal, then the false coins must be either in stack 7 or in stack 8. Compare a coin of each. And again another coin of each. By now, there's only 2 possible answers, comparing the right coin from stack 7 or 8 with a genuine coin should eliminate the last doubt: 9 measurements.
Case C1b: If the measurement from C1 returns unequal, then the false coins are both in one of the stacks 1 to 6. If you move the same 12 coins to one side of the scale and compare with the other 12 (certainly genuine) coins, then you can identify one coin of each of the 6 stacks as genuine. Now you just need to identify the right stack, which is relatively trivial in 2 measurements (especially since you know which coin one will be overweight and which one underweight):
First let's reduce from 6 stacks to 3 stacks: Compare the candidate overweight coins from stacks 1,2&3 with 3 genuine coins. For the final measurement, you put on one side the candidate overweight coin from one stack with the candidate underweight coin of another stack and compare with 2 genuine coins. Total: 9 measurements
Case C2: If the 5th measurement return unequal, then the false coins have the same weight and are in two stacks that were on opposite sides in one of the first 4 measurements. Suppose stacks 1+3 are heavier than 5+7 (the other case is symmetrical). That means that either stacks 1 and 2 have both a heaver coin, or stacks 3 and 4 have both a heavier coin, or stacks 5 and 6 both have a lighter coin, or stacks 7 and 8 both have a lighter coin. To identify which of the 4 scenarios we compare stacks 1 and 3 (6th measurement), and stacks 5 and 7 (7th measurement). Now we know which two stacks have a false coin and if it's heavier or lighter. By comparing two coins of such a stack, we can identify the false coin. Doing that for both stacks results in 9 measurements.
An attempt to solve it with 7 measurements
Part 1 : possibility analysis
A strict lower bound on possibilies:
We only need to find the two fakes, that is 24x23/2 = 276 possibilies
A reasonlable approximate lower bound:
However, it is impossible to do that without finding out the actual offset of the fakes for most distributions of the fakes (if they are heavy/light compared to the genuine coins and other fake). Also solving the relative weight of the coins will therefor be almost the same problem in practice and has a lot more possibilities:
- 2 equal fakes: 24x23/2 = 276 possibilies
- 2 cancelling fakes: 24x23 = 552 possibilies
- a heavy and less heavy fake: 24x23 = 552 possibilies
- a heavy and less light fake: 24x23 = 552 possibilies
- a light and less heavy fake: 24x23 = 552 possibilies
- a light and less light fake: 24x23 = 552 possibilies
Part 2 : an (approximate) lower bound
When using the balance scale we can distinguish 3 states.
When using the weighing scale we can distinguish:
- 3 states for case 1: 0,1 or 2 fakes
- 3 states for case 2: the light fake, the heavy fake or 0/2 fakes
- 4 states in the other cases: no fake, lesser fake, greater fake, both fakes
So the weighing scale is superior , and should be used often!
Now, in theory, we can with the first measurement split the possibilities in 3:
- half of case1+2 solvable in 3log(414) = 5.48 tries
- half of case1+2 solvable in 3log(414) = 5.48 tries
- all of case 3..6; solvable in 4log(2208) = 5.55 tries
So the lower bound is around 6.5
Although it is still not proved that 6 is impossible if we only have to determine the position of the fakes, it is extremely unlikely.
On the other hand 6.5 is 'far' from 7. Making it likely, but not certain, that a solution that only requires 7 measurements exists.
added note: If weighing is used, we have the additional complication that the genuine weight is not known. That is likely to resolve itself however, since as long as we do not know it, we do not have 4, but infinite possible results of the next weighing. Thus, the acquired lower bound does not need a significant increase for that reason.
Part 3: A strategy to (attempt to) get an actual solution with 7 measurements.
When using the weighing scale we initially (after 1 or 2 measurements) cannot conclude much, while the balance scale can immediately discard around 2/3rd of the possibilities. It seems attractive to at least get some answers fast. For example weigh one half and then the other half, then we can at least know if the fakes are distributed 1-1 or 2-0. I could not get that to work however. And it is not needed!
With the weighing scale we can always reason backwards after we have enough data. Then however we must make sure that no big problem area's can emerge. To make sure of that taking orthogonal slices of half the coins seems best. We can do that 3 times, and then are down to groups of 3. Taking 2 of each 3 seems a useful 4th measurement (better than 1 of each , since it leaves only one coin completely unmeasured)
So my (initial) strategy:
Divide the coins in 8 groups of 3: {a,b,c,d,e,f,g,h}.
Measure orthogonal slices; abcd,abef, aceh, nr1+2 of each group.
Part 4a Testing the strategy with a (difficult?) case:
Case 1: all measurements suggest the same weight:
the first 3 measurements showed 12Q and the last one 16Q for some weight Q
- Q is the genuine weight.
Then the fakes must be canceling each other and that is only possible if they are the number 1 and 2 of a group.
- Q is not the genuine weight. That means that the fourth group has at least one fake.
If that one is in b..g, the 1 or 2 groups that do not measure those must have an identical fake. Then the offset of the 4th group can only be 1 or 2 times that offset, but it needs to be 16/12 times the offset. -> contradiction, thus the fakes are in a+h.
Possibilities if the genuine weight is Q:
nr 1+2 of 1 of the 8 groups.
Possibilities if the genuine weight is Q+x:
a1 or a2 Q-11x and h1 or h2 Q-3x
a1 or a2 Q-15x and a3 Q+5x
a3 Q-11x and h1 or h2 Q-15x
The 5th measurement: If we end up with canceling fakes after this measurement, only 5 (having 10 possibilities) can be distinguished enough with the remaining 2 measurements. (weigh 3 and then balance or weigh 1 new group). So we weigh b1..d1.
- if 3Q, they are genuine: we can weigh e1..g1 and the either balance them or measure h1 to distinguish the 5 possibilities.
- if 3Q+y the remaining possibilities are:
The true weight is Q
- b1 or c1 or d1 weigh Q+y the corresponding nr2 Q-y
The true weight is Q+y/3
- a1 or a2 Q-11y/3 and h1 or h2 Q-y (and the rest Q+y/3)
- a1 or a2 Q-15y/3 and a3 Q-5y/3 (and the rest Q+y/3)
- a3 Q-11y/3 and h1 or h2 Q-15x
6) We measure a combo that discerns the different true weight cases and splits up the true weight is Q case.
Note that now the power of the measuring scale really shows.
Weigh h1h2a3b1f1
- 5Q: c1+c2 or d1 + s2 do not weigh Q ( 7) weigh c1)
- 5Q+y: b1+ b2 do not weigh Q (already done)
- 5Q+y/3: a1 or a2 weighs Q-11y/3; h1 or h2 weighs Q-y; (the others Q+y/3) ( 7) weigh a1+h1 to distinguish the 4 cases)
- 5Q-y/3: a1 or a2 weighs Q-15y/3; a3 is the other fake ( 7) weigh a1)
- 5Q-23y/3: a3 weighs Q-11y/3; h1 or h2 Q-15x ( 7) weigh h1)
So the presumed most difficult case of equal average weights is solvable in 7 measurements when using this strategy.
Part 4: An actual solution:
Let's assume that two fake coins are heavier than others and equal in weigh to each other. Let's divide 24 coins into 3 groups of 8 coins. Let's weigh each two groups on a balance. After 2 weighing I know which groups have fake coins. There are two possibilities: one fake in two groups (case A) or two fakes in one group (case B). Case A: 8 coins (1 fake), 8 coins (1 fake), 8 coins (0). Case B: 8 coins (0), 8 coins (0), 8 coins (2 fakes). Let's simplify: A: 8(1), 8(1), 8(0); or B: 8(0), 8(0), 8(2).
First weigh-in possible outcomes: both pans of balance are equal, which means A: 8(1), 8(1) or B: 8(0), 8(0); or one pan of balance is heavy, which means A: 8(1), 8(0); or B: 8(2), 8(0). In former one we can measure one of the measured groups (A:8(1) or B:8(0)) with another unmeasured (A:8(0) or B:8(2)). If unmeasured is lighter than the measured then it is case A because 8(1)(measured)=8(1)(measured)>8(0)(unmeasured). Else if unmeasured is heavier than the measured then it is case B because 8(0)(m)=8(0)(m)<8(2)(unm). So far we did 2 measurements.
Case A: 8(1), 8(1), 8(0). In this case we totally disregard 8(0) because there is no fake coin. Now, let's focus on each of 8(1). Next measurement (case A 1st measure) we find 4(1), 4(0). After that (case A 2nd measure) we find 2(1), 2(0). Then (A 3rd m) we find the exact fake coin (1(1), 1(0)) in that group 8(1). In this case it took us 3 weigh-ins to find fake coin. Another 3 weigh-ins to find the second fake coin in the second 8(1). So total of 2 measurements until we reach case A, and then 6 measurements in case A. So total of 8 measurements altogether.
Case B: 8(0), 8(0), 8(2). In this case we totally disregard 8(0) groups, instead we focus on 8(2). First weigh-in of case B: 4(0), 4(2) or 4(1), 4(1). In the latter (4(1), 4(1)) it will take us 2 more measurements to find fake coin in 4(1). So each 4(1) will take 2 more measurements, 4 in total; 1 measurement in case B until 4(1), 4(1) point; and 2 more measurements before case B. 7 measurements altogether in this part (4(1), 4(1)) of case B.
Now, 4(0), 4(2) of case B. We disregard 4(0) and focus on 4(2). Next measure we find either 2(2), 2(0) or 2(1), 2(1). In 2(2), 2(0) we reached the result because both fake coins are there. So far 2 measures until case B; 1 more in case B to reach 4(0), 4(2); and 1 more to reach 2(2), 2(0). Altogether 4 measurements in this way.
Now, 2(1), 2(1) of 4(0), 4(2). It will take 2 measures to find fake coins because it was heavy than the original coins. 2 measure until case B; 1 more until 4(0), 4(2); 1 more until 2(1), 2(1); and 2 more to find exact fake coins. In total of 6 measurements in this case of B.
I tried to detail all the weigh-ins as best as I could. The most weigh-ins is 8. I got the help of my friends: Bazarbay Halmedov and Kerven Durdymyradov, both from Turkmenistan IMO team. Thanks to them and you all for nice questions and support.
edit: Alternative (nicer?) solution using a lot of weighing
First note that with the weighing scale we sometimes can distinguish more than 3 states (which I use once below)
Make 4 groups a,b,c,d; each with coins 1..6
weigh ab, bc, cd
Case1: Not all weights the same:
4) weigh a (now you also know the weight of b,c,d, and thus in which group or 2 groups they are**)
If fakes from 1 group (then non cancelling)
5) weigh half of each group (due to non cancelling fakes we know if 0,1,or 2 fakes)
- if 1 6)7) balance to find the fakes in their 2 half-groups
- if 0/2 6) measure 14 of each group 7) measure 25 of each group (done in 7)
If fakes from 2 groups
5)6) and 7)8) balance to find the fakes in their 2 groups **
** not identifyable if 2 equal heavies/2 equal lights
Then weigh 123 of one heavy and one light group. If twice that weight is:
- weight light group -> no fake and fakes are heavy
- weight light group + dif (i.e. weight heavy group) -> no fake and fakes are light
- weight light group + 2x dif -> a heavy fake
- weight light group - dif -> a light fake
6) and 7)8) balance to find the fakes in their 2 groups (of 3 resp 6)
Case2: All weights the same: (canceling fakes in one group )
4) weigh 123 from each group
= 123 canceling or 456 canceling
5) weigh 14; 6) weigh 25 7)8) balance to find low from 8 candidates
> 123 heavy 456 light
5) balance 1-3 6) balance 4-6 and 7)8) balance to find low from 4 candidates
Original solution
To do it in 8 measurements with the balance scale:
Measure 12 coins, if equal measure the other 12 else swap half of them and measure again.
With 8 groups of 3 named a,b,c,d,e,f,g,h this leads to 4 cases:
Case 1: ab>cd ac=bd
Case 2: ab>cd ac>bd
Case 3: ab=cd ef>gh
Case 4: ab=cd ef=gh
Case 1: both fakes in abcd and sometimes cancelling
ab>cd ac=bd a>b c>d (a is heavy d is light) a1-a2 d1-d2 (6)
ab>cd ac=bd a=b a=e (c is light d is light) c1-c2 d1-d2 (6)
ab>cd ac=bd a=b a>e (a is heavy b is heavy) a1-b1 b1-b2 (6)
Case 2: a heavy or d light (and dominant over b,c if the other fake is there)
ab>cd ac>bd ef=gh b=c (both fakes in ad) a-e, d-e (+2(at most) = 8)
ab>cd ac>bd ef=gh b>c (fake in ad + bc) (+2+2=8)
ab>cd ac>bd ef>gh (fake in ad + efgh) (+2+3=8)
Case 3: both fakes in efgh
ab=cd ef>gh e=f g=h (e+f heavy or g+h light) a-e (+2 =7)
ab=cd ef>gh e=f g>h (lightest in h + fake in gh) a-g (+2=7)
ab=cd ef>gh e>f g=h (heaviest in e + fake in ef) a-f (+2=7)
ab=cd ef>gh e>f g>h f=g (heavy in e + light in h) (+2=7)
ab=cd ef>gh e>f g>h f>g (heavy in e+g or light in f+h) (+3=8)
Case 4: canceling fakes in abcd of efgh
ab=cd ef=gh bf=ae cg=dh (2 canceling fakes within one group) ->see below
ab=cd ef=gh bf=ae cg>dh (c heavy + d light or g heavy + h light) c-g (+2=7)
ab=cd ef=gh bf>ae b=f (a light + cd light or e light + gh light) a-e (+3=8)
ab=cd ef=gh bf>ae b>f (b heavy acd light) (+3=7)
Case 4.1, second half
compare the first of each group 4vs4 and then the second of each group 4vs4 to determine the fake positions within the group/isolate the fakes.
then use measurement 7+8 to determine the group
