8
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

8
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ You are both right, silly typos. Thanks, I corrected the post. $\endgroup$
    – Florian F
    Jan 20 at 21:08
  • $\begingroup$ Florian, I think user rudra was trying to leave a comment on your answer, “but by this we could only find 1 coin what about the other one ?”. As a new user rudra lacks the reputation to leave comments. $\endgroup$ Jan 22 at 9:54
  • $\begingroup$ Ah yes, the usual problem. The answer is that no, you find both coins. The instructions below the set of possibilities for each case tell you how you can differentiate the four cases. You can find which of the 4 boards is the correct one and that gives both fake coins. $\endgroup$
    – Florian F
    Jan 22 at 12:39
  • $\begingroup$ User rudra has posted a new answer in which they state they don’t completely understand your answer. $\endgroup$ Jan 25 at 20:13
  • $\begingroup$ OK I tried to explain it in more detail. $\endgroup$
    – Florian F
    Jan 25 at 21:33
0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ It looks like you got what I said but I deleted my answer $\endgroup$
    – PDT
    Jan 22 at 22:18
  • $\begingroup$ Give it a quick read $\endgroup$
    – PDT
    Jan 22 at 22:20
  • $\begingroup$ What do you mean by give it a quick read? Are you saying I should reread my solution? I did that and didn't find any issues with it. $\endgroup$
    – Stevish
    Jan 24 at 0:22
  • $\begingroup$ My bad I was talking about the solution that I deleted, I undeleted it for you to read and then deleted it again, it seems we have a similar approach $\endgroup$
    – PDT
    Jan 24 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.