Find the Heavier Coin of 12 in 3 Weighings

Date: 11/17/96 at 15:34:14
From: Daniel R. True
Subject: (no subject)

Twelve coins are in a bag.  They all look alike but one is counterfeit 
and either lighter or heavier than the others.  Explain how to use a 
balance scale to find the fake coin in exactly 3 weighings AND 
determine if it is lighter or heavier than the others.

Thanks!

Date: 11/18/96 at 17:40:59
From: Doctor Wilkinson
Subject: Re: (no subject)

This is a classic puzzle.  There are a number of very clever 
solutions.  For starters, you might want to check out:

  http://home.wxs.nl/~faase009/Ha12coins.html   
and
  http://mathforum.org/dr.math/problems/schwartz.8.6.96.html   

If you want to work on it a little more on your own, I can get you
started.

You probably noticed that the number of coins you weigh at a time is 
important. For example, if you start out just weighing two coins 
against two and the two sides weigh even, you have eight coins left
and only two weighings, and you're just not going to be able to get
enough information. On the other hand, if you weigh five against
five on the first weighing, you're in great shape if they weigh even,
but you've got an awful lot to find out in just two weighings if one 
side weighs heavy. Four against four feels like a good place to start. 
So let's try weighing coins 1, 2, 3, and 4 against coins 5, 6, 7, 
and 8.

The easy case is when it comes out even. Now you've got a stock of
coins that you know are OK, and four coins you know nothing about
except that the bad coin is among them. So weigh 1, 2, and 3 against
9, 10, and 11. If they weigh even, then 12 is the bad coin and you
can use the last weighing to find out whether it's heavy or light.  
I'll let you work out the case where they don't weigh even.

Now suppose the left side comes out heavy in the first weighing. The
choice of the coins for the next weighing is the hardest part of the
puzzle. At this point you know that either one of 1, 2, 3, and 4 is
heavy or one of 5, 6, 7, and 8 is light; and you know that all of 
9, 10, 11, and 12 are good. Now I think you should be able to see
that you don't want to leave four of the coins from the first weighing
out of the second, because if the weighing comes out even, you won't
be able to find the bad coin with just one more weighing. But you can
leave any three of them out. For example, if you leave 1, 2, and 3
out, and the second weighing comes out even, then you know that
one of 1, 2, and 3 is heavy, and you can weigh 1 against 2 to find
out which. Now I'll leave it to you to find a suitable second 
weighing. Remember, you need to consider what to do in each of the
three cases: left balance heavy, left balance light, and even.

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