3 Weighings Problem

Date: 12/09/97 at 12:34:20
From: Paul Midkiff
Subject: 3 weighings problem

Dear Dr. Math,

Here is the problem I've been challenged with:

You have 12 balls that all look and weigh the same except one. You 
have a balance scale to weigh them on. You get three weighings and you 
must tell which ball is different and whether it is heavier or lighter 
than the other 11.

I see how I can determine which is the odd ball (no pun intended) in 
three weighings but I don't see how to tell whether it's heavier or 
lighter.

My challenger swears to me it is solvable. I'm beginning to have my 
doubts. Can you help?

Date: 12/09/97 at 14:49:06
From: Doctor Tom
Subject: Re: 3 weighings problem

Hi Paul,

It's a tough problem. Here's how to solve it in the general case (i.e. 
for 4 weighings, 5 weighings, et cetera):

Here's the algorithm for solving the 12 balls in three weighings
problem. It also happens to solve the 3 balls in two weighings or 39
balls in 4 weighings, or 120 balls in 5 weighings or ..., problems.

First, list all 3 digit combinations of 0, 1, and 2:

    000    100    200
    001    101    201
    002    102    202
    010    110    210
    011    111    211
    012    112    212
    020    120    220
    021    121    221
    022    122    222

For the 4 weighing problem, list all 4 digit combinations, and so on.

Next, cross out all sets with identical digits (000, 111, 222), and 
also throw out all whose first digit change (reading from left to 
right) is not 01, 12, or 20. In other words, 112 is left in because 
the first change is from 1 to 2, but 212 is eliminated, since the 
first change is from 2 to 1.  This leaves:

    (a)   001
    (b)   010
    (c)   011
    (d)   012
    (e)   112
    (f)   120
    (g)   121
    (h)   122
    (i)   200
    (j)   201
    (k)   202
    (l)   220

where a, b, ..., l are the balls.

Now, for the first weighing, weigh all the balls with a 0 in their 
first position against all the balls with a 2 in the first position, 
in other words, (a, b, c, d) are weighed against (i, j, k, l). 
If the balls with the 0 are heavier, write down 0; if the balls 
balance, write 1, otherwise; write 2.  Next, weigh all balls with 
a 0 in the second position against all balls with a 2 in the second 
position (a, i, j, k) against (f, g, h, l), and write down the digit 
corresponding to the result of the weighing, and do it again for the 
third position in the third weighing.

As an example, suppose ball f (120) is heavy.  In the first weighing, 
f is not involved, so write down 1.  Next, (f, g, h, l) -- the "2" 
balls are heavier than (a, i, j, k) so write down 2. Finally, in the 
weighing (b, f, i, l) versus (d, e, h, k), the "0" side (b, f, i, l) 
is heavier, so write down a 0.  You have written "120" - the code for 
ball f - so f is the heavy ball.

If you find that the combination you write down is not in the list, 
say 211, then change the 2s to 0s, the 0s to 2s, and leave the 1s 
alone, giving 011. This is ball c, but since you had to flip the 
digits, ball c is lighter.

With N weighings, there are 3^N combinations, of which we eliminate 3
and cut the remainder in half, so for 4 weighings, one can distinguish
among (3*3*3*3-3)/2 = 39 balls, etc.

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