Finding One Coin of 12 in 3 Steps

Date: 8/6/96 at 19:25:17
From: Josh Schwartz
Subject: Finding One Coin of 12 in 3 Steps

There is a pile of twelve coins, all of equal size.  Eleven are of 
equal weight.  One is of a different weight.  In three weighings find 
the unequal coin and determine if it is heavier or lighter.

Our teacher said a hint was 3 piles of four but without knowing 
heavier or lighter, I don't see how to get it in 3 weighings.

Thanks for the help

Date: 8/6/96 at 21:14:28
From: Doctor Robert
Subject: Re: Finding One Coin of 12 in 3 Steps

I had already worked this problem out for someone else using pills. 
The setting of the problem, as I remember it, goes something like 
this.  

A wise man has committed a capital crime and is to be put to death.  
The king decides to see how wise the man is. He gives to the man 12 
pills which are identical in size, shape, color, smell, etc. However, 
they are not all exactly the same. One of them has a different 
weight. The wise man is presented with a balance and informed that all 
the pills are deadly poison except for the one which has a different 
weight. The wise man  can make exactly three weighings and then must 
take the pill of his choice.  

Remember that the only safe pill has a different weight, but the 
wise man doesn't know whether it is heavier or lighter.

Most people seem to think that the thing to do is weigh six pills 
against six pills, but if you think about it, this would yield you no 
information concerning the whereabouts of the only safe pill. 
 
So that the following plan can be followed, let us number the pills 
from 1 to 12.  For the first weighing let us put on the left pan pills
1,2,3,4 and on the right pan pills 5,6,7,8.  

There are two possibilities.  Either they balance, or they don't.  If 
they balance, then the good pill is in the group 9,10,11,12.  So for 
our second weighing we would put 1,2 in the left pan and 9,10 on the 
right.  If these balance then the good pill is either 11 or 12.  

Weigh pill 1 against 11.  If they balance, the good pill is number 12.  
If they do not balance, then 11 is the good pill.  

If 1,2 vs 9,10 do not balance, then the good pill is either 9 or 10.  
Again, weigh 1 against 9.  If they balance, the good pill is number 
10, otherwise it is number 9.   

That was the easy part.  

What if the first weighing 1,2,3,4 vs 5,6,7,8 does not balance? Then 
any one of these pills could be the safe pill.  Now, in order to 
proceed, we must keep track of which side is heavy for each of the 
following weighings.  

Suppose that 5,6,7,8 is the heavy side.  We now weigh 1,5,6 against 
2,7,8.  If they balance, then the good pill is either 3 or 4.  
Weigh 4 against 9, a known bad pill.  If they balance then the good 
pill is 3, otherwise it is 4.  

Now, if 1,5,6 vs 2,7,8 does not balance, and 2,7,8 is the heavy side, 
then either 7 or 8 is a good, heavy pill, or 1 is a good, light pill. 

For the third weighing, weigh 7 against 8.  Whichever side is heavy is 
the good pill. If they balance, then 1 is the good pill. Should the 
weighing of 1,5, 6 vs 2,7,8 show 1,5,6 to be the heavy side, then 
either 5 or 6 is a good heavy pill or 2 is a light good pill. Weigh 5 
against 6.  The heavier one is the good pill.  If they balance, then 2 
is a good light pill.

I think that one could write all of this out in a nice flow chart, 
but I'm not sure that the flow chart would show up correctly over 
e-mail.    

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

Date: 11/11/98 at 12:07:39
From: Tom Manning
Subject: Three Weighings

There is another way of looking at the three weighings problem that can
give you more information.

If the initial weighing of 1,2,3,4 against 5,6,7,8 balances, you can
correctly deduce that the unequal (heavier or lighter) pill is in the 
set 9,10,11,12. If you weigh 9,10 against 1,2 and they balance, you can
correctly deduce that the unequal pill is 11 or 12. If pill 11 weighs
the same as pill 1, you can correctly deduce that 12 is the unequal pill.

But the problem is phrased so that it requires you to know whether pill 
12 is *heavier or lighter*.  Here is another solution:

Suppose after the first weighing that the set 1,2,3,4 balances with 
5,6,7,8.

Now weigh 9,10,11 against 1,2,3. If they balance, then pill 12 is the
unequal pill. Weigh pill 12 against pill 1 to determine whether pill 12 
is heavier or lighter.

If instead the set 9,10,11 is *heavier* than 1,2,3, then any one of pills
9,10,11 could be heavier. Weigh pill 9 against pill 10; if they balance,
then pill 11 is heavier. If they do not balance, then the pill that weighs
more is the heavier pill.

If the set 9,10,11 is *lighter* than 1,2,3, then any one of pills 9,10,11
could be lighter. Weigh pill 9 against pill 10; if they balance, then pill
11 is lighter. If they do not balance, then the pill that weighs less is
the lighter pill.

Date: 04/17/2002 at 10:09:37
From: Lars Prins
Subject: General solution 12 coins problem

Below, you will find my general solution to the 12 coins problem. It 
is a systematic and rather elegant approach (in my humble view). Have 
fun.

Lars Prins
--------------------
Of 12 coins, one is counterfeit and weighs either more or less than 
the other coins. Using an old-fashioned balance with two scales, and 
performing only three measurements, you have to find out which coin is 
counterfeit, and whether it is lighter or heavier then the other 
coins. How would you do that?

The basic idea of this solution is to perform the three measurements, 
look at the result of each measurement, and then look at the way each 
coin has participated in the measurements to identify the only coin 
that could have caused this particular combination of results.

For instance, if the three results are: equal (0), right side heavier 
(R), left side heavier (L), or, in short, 0RL, then it must have been 
the coin that was

    not in the first measurement,
    on the right in the second measurement,
    on the left in the third measurement,

and that coin is heavier than the others, or (mirrored) the coin that 
was 

    not in the first measurement,
    on the left in the second measurement,
    on the right in the third measurement,

and that coin is lighter than the others. 

Note how the measurement result 0RL and the participation of a heavier 
coin in the measurements coincide.

So all we have to do is to distribute the 12 coins over the scales of 
the three measurements in such a way that no coin participates in the 
three measurements in the same way (or mirrored) as any other coin. 
The distribution below is one of many possible distributions that 
fulfills this requirement:

    1, 2, 7, 10   against   3, 4, 6, 9
    1, 3, 8, 11   against   2, 5, 6, 7
    2, 3, 9, 12   against   1, 4, 5, 8

If the measurements result in 0RL, then it can be seen from this 
distribution that coin 8 is lighter than the other coins. No other 
coin can explain the outcome 0RL. 

DONE.

We have thus found a solution to the problem. But how can such a 
solution be found? I.e., how can a distribution of coins over the 
measurements such as the one above be found? And why should there be 
four coins on each side of the balance in each measurement? The answer 
is in the list of logical steps below.

Each measurement has three possible results: equal (0), right side 
heavier (R), or left side heavier (L). The three measurements together 
can therefore have a total of 3x3x3 = 27 different outcomes, namely 
any possible combination of 3 letters out of 0, L, and R, i.e.,

    000, 00L, 00R, 0L0, 0LL, 0LR, .... , RRL, RRR.

We are looking to find the right one among 24 different statements, 
i.e., 

    "coin 1 is heavier", "coin 1 is lighter", ... , 
    "coin 12 is lighter".

We need to map each statement to an outcome, so that if that outcome 
occurs, the statement to which it maps must be true. Part of such a 
mapping table could be:
	
    LR0   means   "coin 1 is heavier"
    RLR   means   "coin 2 is heavier"
    etc.

This mapping table serves two purposes. It identifies the counterfeit 
coin and its weight after having performed the measurements, but it 
also tells us where to put each coin in each measurement. For 
instance, since we want LR0 to mean "coin 1 is heavier," coin 1 must 
participate in measurement 1 on the left side, in measurement 2 on the 
right, and not at all in measurement 3.

Outcome 000 is useless to us since it means that the counterfeit coin 
was never part of a measurement and we can not tell whether it was 
lighter or heavier than the others. This leaves 26 possible outcomes 
that must be mapped to 24 statements.

If LR0 means "coin 1 is heavier," then RL0 (its mirror outcome) must 
mean the opposite, i.e., "coin 1 is lighter." This is so because 
mapping LR0 to "coin 1 is heavier" determines where coin 1 occurs in 
the three measurements, and if that coin is lighter instead, the 
measurements will result in the mirror outcome.

We can therefore group the 26 outcomes into 13 pairs (each outcome 
with its mirror outcome). The table can now be reduced to mapping 12 
statements about coins being heavier to 12 outcomes (each outcome 
taken from a different pair).

We have one pair of outcomes too many. If we make a list of all 
outcomes, and count the numbers of L's and R's (not counting 0's) that 
appear in the first position of each of the outcome strings, we will 
end up with the number 9 (or 18 when including mirror outcomes). This 
means that 9 coins would participate in the first measurement. 
Counting L's and R's in the second and third position would also yield 
9. Since we can not distribute 9 coins evenly over 2 scales, the pair 
of outcomes we are not going to use should have an L or R in each 
position, such as LLL and its mirror outcome, RRR. Not using that pair 
will leave 8 coins in each measurement. Alternatively, any other pair 
of outcomes with three letters, e.g., (LRR, RLL), can be dropped from 
the outcomes and a correct distribution can still be found using the 
remaining 12 outcome pairs.

We are now left with 12 outcome pairs and 12 statements about each 
coin being heavier. Since the numbering of the coins is irrelevant, 
the only remaining choice we have is which outcome of each pair we 
will use in the table. If we now start to map "heavier" statements to 
outcomes arbitrarily, we run the risk of ending up with 6 coins on the 
left and 2 coins on the right in a measurement, which isn't going to 
tell us much. We must ensure that in each measurement (position in the 
outcome string), there are as many coins on the left (symbols L) as 
there are on the right (symbols R). We can achieve this by taking a 
mirror outcome if the scales get out of balance.

The rest is a bit of rather straightforward trial and error. Let's 
decide not to use the pair (LLL, RRR). From each remaining pair, we 
pick one outcome in such a way that we have the same number of L's and 
R's in each position of the string. We save the pairs of outcomes with 
two 0's to the end to make it easier to get the scales back into 
balance.

    LLR   \
    LRL    >   3 letters, one of which is different
    RLL   /

we now have two L's in each column against one R, so let's use some 
more R's

    R0R   \
    0RR    >   one 0 and twice the same letter
    RR0   /	

each column has now one R too many

    LR0   \
    0LR    >   one 0 and two different letters
    R0L   /	

we still have one R too many in each column

    L00   \
    0L0    >   two 0's and one letter
    00L   /
	
Since we now have an equal number of L's and R's in each of the three 
columns of the outcomes (namely 4), we have an equal number of coins 
on each side of the scales in each measurement. 

To complete the table, we only need to write down the "heavier" 
statements next to the outcomes (and the "lighter" statement to the 
corresponding mirror outcomes). The numbering of the coins is of 
course irrelevant:

   LLR	"coin 1 is heavier"     RRL  "coin 1 is lighter"
   LRL	"coin 2 is heavier"     RLR  "coin 2 is lighter"
   RLL	"coin 3 is heavier"     LRR  "coin 3 is lighter"
   R0R	"coin 4 is heavier"     L0L  "coin 4 is lighter"
   0RR	"coin 5 is heavier"     0LL  "coin 5 is lighter"
   RR0	"coin 6 is heavier"     LL0  "coin 6 is lighter"
   LR0	"coin 7 is heavier"     RL0  "coin 7 is lighter"
   0LR	"coin 8 is heavier"     0RL  "coin 8 is lighter"
   R0L	"coin 9 is heavier"     L0R  "coin 9 is lighter"
   L00	"coin 10 is heavier"    R00  "coin 10 is lighter"
   0L0	"coin 11 is heavier"    0R0  "coin 11 is lighter"
   00L	"coin 12 is heavier"    00R  "coin 12 is lighter"

As explained before, the left part of the table tells us exactly where 
each coin participates in each measurement. The resulting distribution 
of coins over scales is the one given at the beginning. In addition, 
the table above can be used to find the counterfeit coin after having 
performed the three measurements.