Seven genuine coins have the same weight. Two counterfeit coins also have the same weight. A counterfeit coin is heavier than a genuine coin. Identify the fake coins using a standard balance at most four times.
Clarification: The term “standard balance” refers to a two-pan balance which is used to determine if the object(s) resting on one pan are heavier or lighter or of the same weight as object(s) on the other pan.
This puzzle comes from a 1980 Leningrad Mathematical Olympiad.
Here is a method. Let's name the coins ABC DEF GHI.
Note that if you weigh two groups of 3, ABC vs DEF, then
- If they weigh the same, then ABC and DEF have one fake, or GHI has two.
- If ABC > DEF then either ABC has both fakes, or ABC and GHI both have one.
Now let's weigh ABC vs DEF and ADG vs BEH.
It is clearer if you imagine them in a grid. You weight them by row and them by column.
A B C
D E F
G H I
Wlog, after rearranging the coins and the weighings, we can reduce the results to three cases: : = =, > = and > >.
If for instance you weigh ABC = DEF and ADG < BEH, just rearrange the coins and relabel them as follows:
A' B' C' B E H
D' E' F' = A D G
G' H' I' C F I
Now you have: A'B'C' (= BEH) > D'E'F' (ADG)
and A'D'G' (=ABC) = B'E'H (=DEG)
So that you are in the case > =.
For the case = =, the possible positions of the fakes are:
A B C x o o o x o o o x o o o
D E F = o x o or x o o or o o x or o o o
G H I o o o o o o o o o x x o
You can idenfiy the fake coins if you weigh A vs B, and if equal C vs G.
If you weigh A > B it only happens in the first board. This identifies A and E as fake.
If A < B, similarily, it happens only in the 2nd board. The fakes are E and G.
If A = B you need one more weighings. If C > G then the third board shows the solution, C and F are fake, else you must have C < G as in the last board, where G and H are fake.
For the case > = (ie ABC > DEF and ADG = BEH), you have the following possibilities:
A B C x x o x o o o x o o o x
D E F = o o o or o o o or o o o or o o o
G H I o o o o x o x o o o o x
In that case, finish by weighing C vs G and if equal A vs B.
If C > G, it is last board, C and I are fake. If C < G, it is the 3nd board, G and B are fake. If C = G and A > B then it is the 2nd board, A and H are fake. If C = G and A = B then it is the first board, A and B are fake.
For the last case > >, you can have:
A B C o o x x o o x o x x o o
D E F = o o o or o o o or o o o or o o o
G H I x o o o o x o o o x o o
There, you find the fakes for instance if you weight C vs G, and if equal A vs B. It is similar to the first 2 cases.
Actually, you cover all the cases above by weighing ABC:DEF, ADG:BEH, A:B and C:G.
(ps. This isn't true, in fact, since you might have to relabel the coins, so the last 2 weighing are not always the same).
I started the same way as Florian, but went case by case for each result and I think I wound up with a different answer (I read Florian's after doing mine and I wasn't even smart enough to follow along! Nice work, Florian).
Weighing 1:
ABC <=> DEF
If Weighng 1 (W1) is the same:
ABC and DEF have either 1 or 0 fakes each, so GHI has 0 or 2 in the respective situations. So, for weighing 2, we do DE<=>GH
If W2 is THE SAME, then GHI can't have 2 fakes (because at least one of GH would be fake, and that would be heavier than DE which couldn't also have a fake), and DE are Genuine (because if GHI has no fakes, and DE weighs the same as GH, none of the 4 are fakes) so, DEGHI are Genuine and F (the only one of DEF left) is a fake. Then just weigh A against B (W3) and the Heavy one is also a fake (or, if the same, C is a fake). Done.
If W2 is DIFFERENT, and GH is Heavier, then GHI must have 2 fakes. Here we can use the 3/2 rule where we have 3 coins, 2 of which are fake. Weigh any 2 of them (Let's say G and H), and if they're equal, they're the 2 fakes, but if not, the heavy one (Let's say G) and the one you didn't weigh (I) are fakes. Done.
If W2 is DIFFERENT but DE was heavier, then We know one of those is fake meaning GHI must be genuine, as well as F since only 1 of DEF could be fake. So now we know 1 of ABC is fake and 1 of DE is fake.
Any time we have 3 coins where exactly one is fake, we use this 3/1 rule: weigh any two, and the heavier is a fake (or the third is fake if the two we weighed are the same). So, our 3rd and 4th weighings here will be the 3/1 rule for ABC to see which of those 3 is fake, and a simple weighing of D<=>E to see which of those is fake.
This covers all situations where ABC = DEF
If Weighing 1 is different, then...
Whichever set was lighter must be genuine (If it had even a single fake, there would be no way to make the other side heavier without 2 fakes in it, which would be impossible since there are only 2 fakes). Let's say DEF was lighter, so we rule them out as genuine.
Weighing 2 will be ABC <=> GHI
If they're the same, we know that each side has one fake in it. We can use the 3/1 rule from above on ABC for W3, and on GHI for W4, and we'll have the answer.
If they're different, the heavy side has 2 fakes. We use the 3/2 rule from above and find out answer in 3 weighings!
I think that covers all the possibilities. Is that the same as what Florian found?
