The twelve balls problem.
It seems to
be a “classic problem”, but I encountered it for the first time at the end of
2002. The problem was formulated as follows:
“Assume you
have 12 billiard balls. They look all identical, but one (you don’t know which-one)
has a deviating weight (either lighter or heavier then the others).
Furthermore you can use a balance. This balance can indicate whether the balls placed on the left side are (in total) more heavy, less heavy or of equal weight compared with the balls placed on the right side.”
The
question is: “Can you define an experiment which always will identify the
deviating ball and also indicate whether this ball is more or less heavy than
the other balls?”
After some
puzzling it was not too difficult to design such a scheme. The interesting
discussion came later:
This
problem is a specific case of a class of problems. More generic: you have n
balls with m weightings. Interesting questions:
To start
with the second question: Yes this is possible. I found it the easiest way to
write a recursive algorithm which splits the problem in a number of simpler
problems. I’ve tried to reduce the trial and error part as much as possible,
but I could prevent some (unsuccessful) trying at the end.
The result
of this effort can be checked by pressing the link. People interested in the
source code can get this by sending me an e-mail (billiard@troost.org) But be warned: I
used this problem as a training to learn Phyton. The result is not a “beauty”.
The answer
on the first problem is not too difficult. In fact you should try to find it
yourself, before reading further.
As you have
probably concluded yourself, each weighting has three possible outcomes: left
down, balance or right down. By planning each weighting carefully (each
possible outcome has equal probability), n experiments can differentiate
between 3n possible outcomes.
Going back
to the original problem, 3 weightings deliver maximal 33 =27
different outcomes. Having 1 ball out of 12 either heavier or lighter gives 24
different outcomes, so within the theoretical limit.
There are
physical constraints which do not always make it possible to reach the
theoretical limit (you can not always design experiments in such a way that the
probability of each outcome is 1/3). A
good example is if you add one ball. With thirteen balls, the number of
different outcomes is 26 (2*13), which is still below the theoretical limit of
three weightings (27). It however impossible to design an method to derive in
three weightings which of the 13 balls has the deviating weight and how it
deviates.
Such
physical constraints can be solved by adding a 14th reference (i.e.
of “standard” weight) ball. This doesn’t change the possible outcomes (26
possibilities), but adds a maneuvering space to design a method to solve the
problem.
The program
allows you to set two parameters:
Due to
physical limitations (available stack-space on the server),the maximum number
of weightings is limited. This is not a limitation of the algorithm.
Enjoy!