## Wednesday, August 5, 2009

### Find the fake coin

You have eight coins which look identical. One of them is fake, made of a slightly heavier metal than the others. The difference in weight is too small to feel by hand, but you have a precision scale which can weigh one object (or set of objects) against another.

If you are only allowed to use the scale twice, can you pick out the fake coin from the real ones?

Bonus question: You have twelve coins which look identical. One of them is fake, and has a slightly different weight than the others. You do not know whether it will be heavier or lighter, and you cannot feel the difference by hand. Can you pick out the fake coin if you are only allowed to use the scale three times?

See the solution

DeralterChemiker said...

Take any three coins and weigh them against any other three coins. If they weigh the same, the heavy coin is one of the other two; weigh those two coins against each other, and the heavier coin will be identified.
If one set of three coins is heavier than the other, take two coins from the heavier set and weigh them against each other. If one of those is heavier than the other, the heavy coin has been identified. If those two coins weigh the same, the heavy coin is the third coin from that set of three.

miller said...

Hey, that's exactly right! Congratulations!

Secret Squïrrel said...

Ok, the bonus problem requires a bit more work and a more elaborate decision tree but I'll try to be as succinct as I can. I'll label the coins with letters (A to L) so they don't get confused with my numbering of the steps.

Step 1. Weigh any four coins against any other four, say ABCD - EFGH. The three possible results are: (a) balance, (b) ABCD is heavier, (c) EFGH is heavier.

(a) If they balance, then the fake coin must be one of the others (IJKL). Go to Step 2.1.

OR

(b) If ABCD is heavier, then either one of ABCD is fake and it's heavy OR one of EFGH is fake and it's light. Go to Step 2.2.

OR

(c) If EFGH is heavier, then either one of ABCD is fake and it's light OR one of EFGH is fake and it's heavy. Go to Step 2.3.

Step 2.1. (ABCD balanced EFGH).
Now weigh three known genuine coins (say ABC) against IJK. The three possible results are (a) balance, (b) ABC is heavier, (c) IJK is heavier.

(a) If they balance then L must be the fake. For your 3rd weighing, weigh it against any other coin to see whether it's heavy or light. DONE.

OR

(b) If ABC is heavier then one of IJK is the fake and it's light. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is lighter then that is the fake, otherwise it is the other one (K) and it's lighter. DONE.

OR

(c) Very similar to (a), if IJK is heavier then one of IJK is the fake and it's heavy. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is heavier then that is the fake, otherwise it is the other one (K) and it's heavier. DONE.

Step 2.2. (ABCD heavier than EFGH).
Weigh two coins from each group against one from each group plus two known genuine coins; eg IJKL are known to be not fake so weigh ABEF against CGIJ. The three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier.

(a) If they balance then the fake is one of the others, either D (and it's heavy) or H (light). For your 3rd weighing, weigh DH against IJ. If DH is heavier then D is the fake, if lighter then H is the fake. DONE.

OR

(b) If ABEF is heavier then either A or B are fake and heavy or G is fake and light. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

OR

(c) If CGIJ is heavier then either E or F are fake and light or C is fake and heavy. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

Step 2.3. (EFGH heavier than ABCD).
Perform the same weighing as for step 2.2 - weigh ABEF against CGIJ (IJ known to be genuine). The same three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier (however, the implications of these results are different from 2.2).

(a) If they balance then the fake is one of the others, either D (and it's light) or H (heavy). For your 3rd weighing, weigh DH against IJ. If DH is heavier then H is the fake, if lighter then D is the fake. DONE.

OR

(b) If ABEF is heavier then either E or F are fake and heavy or C is fake and light. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

OR

(c) If CGIJ is heavier then either A or B are fake and light or G is fake and heavy. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

I think that'll do it if someone wants to wade thru and check.

miller said...

Excellent, excellent. I hope you don't mind if I quote your solution later.

s said...

Be my guest!

As an addition, I thought about whether you could include a 13th coin and still determine whether the fake is heavy or light. Not always. However, you will always be able to tell which is the fake (which might be all you need to do).

I tried all sorts of variations on my solution above but in the end I realised that you could just leave this coin (which I'll label 'X' since X is nearly 13 in Roman Numerals ;-) to one side and run thru the exact same procedure for coins A-L.

If X is the fake then the first two weighings (Steps 1 and 2.1) will balance leaving you at 2.1(a) with the slightly modified result that either L or X is fake. If you follow the 3rd weighing and weigh L you will know that X is the fake but not whether it is heavy or light.

In all other cases you will still be able to determine both data; ie 12 out of 13 times you will know all, and 1 out 13 times you will know only which coin is the fake.

Secret Squïrrel said...

Er, that's me above. Autocomplete didn't.

Jack Wert said...

The better puzzle is the 12 coin one:
You have 12 coins, visually identical, but one differs in weight from the others - to be idengified in just three (3) weighings of the two pan balance.
Yet better: 120 coins, the odd weight one to be identified in just five (5) weighings.
Jack Wert