Copyright ©2017 by Paul Niquette. All
|hen Nina posed
the question to a certain
puzzle-master, he said, "That's easy: Put four balls in
each of the two trays. If they balance, the Odd Ball is the one remaining.
If they do not balance, take the four balls in the
higher tray and distribute them evenly onto the balance
scale. Of course they won't balance, so take the
two balls in the higher tray and distribute them onto
the trays, and voilą, the higher tray holds the Odd Ball."
"Well done," said Nina. "How many weighings did you need?"
The puzzle-master counted on his fingers. "Three," he said.
She shook her head. "The Odd Ball can be found with only two weighings." Nina saw the quizzical look on the puzzle-master's face. "Divide the nine balls into three equal groups," she explained. "Distribute two groups onto the trays. With your first weighing, you can immediately determine which group must have the Odd Ball. Take two balls from that group and distribute them onto the two trays, and voilą, with your second weighing, you have found the Odd Ball."
The puzzle-master was flabbergasted.
ophisticated solvers may want to test Nina's algorithm for finding the minimum number of weighings with other quantities -- or generalizing it for finding the Odd Ball in a set of n balls. That division by three seems to be the ticket. Here are a few observations.
In integer arithmetic int(n/3) produces three quotients, two of which are equal to each other and thus suitable for the balance scale. The third adds the remainder, such that rem(n,3) = 0 or 1 or 2 period.Another challenge is to modify the puzzle so that it is unknown whether the Odd Ball is lighter or heavier than the other n-1 balls.
Finally, the puzzle-master's solution is not quite so bad compared to Nina's as depicted above. On average, it requires only 2.778 weighings, not 3.000. So there.
Odd Ball Epilog
areful solvers will look closely at the illustrations in the Odd Ball puzzle and likely decide that the trays on the balance scale cannot accommodate three balls each. A reasonable assumption would be that each tray is able to hold only one ball at a time. If so...
Giving each of nine balls a numerical identification, the first weighing compares 1 with 2. If either happens to be the Odd Ball, the puzzle has been solved with only one weighing.
The probability that the Odd Ball is found in one weighing is [2/9] = 0.22...2.For the second weighing, the careful solver has three choices: comparing 3 with either 1 or 2, or comparing 3 with 4.
The respective probabilities for favorable outcomes are [7/9](1/7) = 1/9 = 0.11...1 and [7/9](2/7) = 2/9 = 0.22...2, so comparing 3 with 4 is the better choice.
At this point, one can say that each weighing compares two balls independent of all other weighings. These are 1~2, 3~4, 5~6, 7~8. Thus no more than four weighings are needed.
If the Odd Ball is not 1 or 2, then two or more weighings are needed.Here is a simple table that enables us to ascertain the average number of weighings needed...