Finding the Counterfeit Coin (1 of 9)

Date: 05/29/98 at 22:40:09
From: May
Subject: 9 Coins, One Counterfeit

I have 9 coins, one of which is counterfeit. It is either lighter or 
heavier than the others. How do I locate the counterfeit coin, in 
three weighings only, considering every possible outcome?

I've tried it endlessly, and I can do it with 12, but complications 
come along when I try to use the same method for 9.

Thanks!

Date: 06/11/98 at 01:12:50
From: Doctor Jeremiah
Subject: Re: 9 Coins, One Counterfeit

Hi May:

Assume we are using a balance. A balance does not measure the weight 
of the object; it compares the weights of two objects and reports 
which is heavier.

We label the coins with the numbers 1 through 9 and refer to the coin 
by number. If we compare 1, 2, 3, and 4 with 5, 6, 7, 8 and leave 9 
off to the side, and both sides have the same weight, then 9 is bad.  
If they have different weights, one of the eight we weighed is bad and 
there is no way to figure it out in two more weighings. So starting  
this way will not work.

Starting again, we compare 1, 2, 3 with 4, 5, 6 and leave 7, 8, 9 off 
to the side. If they have the same weight, then one of 7, 8, or 9 is 
bad. It can be shown which one is bad with two more tests.

If the left is heavier or the right is heavier then one of 1, 2, 3, 4, 
5, or 6 is bad. We compare 1, 5 with 4, 2 and leave 3, 6 off to the 
side. If they have the same weight then either 3 or 6 is bad. It can 
be shown which one is bad with one more test.

If the side that is heavier this time was the same side that was 
heavier last time, then swapping 2 with 5 had no effect, and so it 
must be either 1 or 4. It can be shown which one is bad with one more 
test.

If the side that is heavier this time was not the same side that was 
heavier last time, then swapping 2 with 5 had an effect, and so it 
must be either 2 or 5. It can be shown which one is bad with one 
more test.

When I say, "It can be shown which one is bad with one (two) more 
test(s)," what I mean is that because you can find the bad coin when 
there are 12 of them, it should be pretty easy for you to figure out 
this last part. However, if you would like another hint, please write 
back.

-Doctor Jeremiah,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/