A Solution To The 12 Ball Problem
Statement of the problem: You have 12 balls, one of which is heavy or
light. In 3 weighings, determine which ball is odd and whether it is light
or heavy.
Label the 12 balls 1, 2, etc. to 12. Perform the following 3 weighings:
1 2 3 4 5 6 7 8
1 4 8 9 2 3 11 12
3 7 9 12 1 2 5 10
If the left side goes
Up, Up, Down, then 1 is light
Up, Down, Down, then 2 is light
Up, Down, Up, then 3 is light
Up, Up, Even, then 4 is light
Up, Even, Up, then 5 is heavy
Even, Up, Up, then 9 is light
Up, Even, Even, then 6 is heavy
Even, Even, Up, then 10 is heavy
Even, Up, Even, then 11 is heavy
Down, Up, Even, then 8 is light
Down, Even, Up, then 7 is light
Even, Down, Up, then 12 is light
Changing all words Up to Down and Down to Up (and leaving Even alone,) the
12 other possibilities are given by changing light to heavy and heavy to
light.
Note: There are many other ways of presenting the solution to this
interesting problem. The one above reflects the particular way it came out
the way I did it. I suppose I could have stated it so the right hand side
always read light. This of course would mean I would simply have to change
the 5th weighing for example to read Down, Even, Down, then 5 is light.
etc.
How I came up with the list above is a complicated thing to explain.
Basically, I tried to remember how many balls you need to use on each side
(for this problem was given to me many years ago and I have seen the
solution; I played with 3 on each side for a while and then decided 4 on
each side was needed.) Then I decided listing the unique Up/Down/Even
possibilities would be useful. Then it was a matter of starting with the
first weighing (1 2 3 4 5 6 7 8,) and arbitrarily deciding ball 1 was
light (my first Up/Down/Even code happened to be Up, Up, Down, (or UUD in
code form (see musings, below))) and this would happen provided ball 1 was
light and I put ball 1 on the left side of the scale in the second weighing
and on the right side in the 3rd. So that's just exactly what I did. The
next Up/Down/Even code in my list similarly "generated" where ball 2 would
need to be placed in the last two weighings. Instead of wasting many hours
using my brain, guesswork etc. etc. I realized letting the three letter
codes generate the placement of the odd ball was the way to go.
In the whateverit'sworth department, doing all this reminded me of DNA, the
four "bases" ATCG (Adenine, Thymine, Cytosine and Guanine) and how this 4
letter code dictates the helix of life and I eventually convinced myself
that UUD, UDD, UDU, UUE, UEU, EUU, UEE, EEU, EUE, DUE, DEU and EDU were
the building blocks of the 12 ball problem and well ...
Problem solving is truly amazing ...
A completely different approach is given in the graphic below.
It was obtained from http://www.curiouser.co.uk/ and is
shown here with permission.
http://www.primepuzzle.com/leeslatest/12_ball_solution.html - Friday, June 09, 2006