Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search