Odd Ball -- Solution

Odd Ball

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.

After the first weighing, the algorithm iterates with the int(n/3) as its input for unbalanced cases and int(n/3)+rem(n,3) for balanced cases.

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.
The probability that two or more weighings are required is [7/9] = 0.77...7.

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.
The probability that three or more weighings are needed is [7/9](5/7) = 5/9 = 0.55...5.

You can now answer the puzzle question: "How would you find the Odd Ball?"

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.
If the Odd Ball is not 1, 2, 3 or 4, then three or more weighings are needed.
If the Odd Ball is not 1, 2, 3, 4, 5 or 6, then four weighings are needed.

Here is a simple table that enables us to ascertain the average number of weighings needed...

Assigned Odd Ball Number	1	2	3	4	5	6	7	8	9
Weighings Needed to Find the Odd Ball	1	1	2	2	3	3	4	4	4

The Odd Ball can be assigned any number 1, 2, ... 9. We calculate the simple average of the needed weighings to find the Odd Ball by summing the needed weighings for each case and dividing by the number of cases: 24/9 = 2²/3 weighings on the average.

Home Page Puzzle Page Logic and Reasonings The Puzzle as a Literary Genre