Here's a riddle from a friend's website - "You have twelve billiard balls. Eleven of them are normal and have exactly the same weight, but one may be a little heavier or lighter than the rest. Unfortunately, you don't know which ball is the bad one, and you don't know whether it's too heavy or too light. In fact, there may not be a bad ball at all. Can you determine which ball, if any, is not normal, with no more than three tests on a balance scale?"

A balance scale has two dishes to hold things. If the things in each dish weigh exactly the same, the scale balances. Otherwise, it shows which side is heavier.

- Do you already know how to solve the problem?
- Does it seem like a problem you've already solved?
- Try out a few ideas, but don't get bogged down. It's a hard problem.

Let's try a simpler problem - "You have five billiard balls, and you know one of them is too heavy. The rest all weigh the same. How many tests with a balance scale do you need to find the odd ball?"

If that's still too hard, try it with only two or three balls.

Try it out.

If you have a balance scale, great! Find four things that weigh the same and one that's heavier. Try five numbered envelopes, four with a penny and one with a quarter. See if you can figure out the heavy one by just using the scale.

If you don't have a scale, get creative. Take five playing cards or numbered pieces of paper. Have a partner pick one of them as the "heavy" without telling you which. You can put the cards you want to test into two piles, and your partner either points to the heavy pile or says "Balance!".

Remember that you don't have to use all the "balls" every time. Weighing two balls against three probably wouldn't help much.

- How many tests do you need? Are you sure that's always enough?
- Can you explain your method so that someone else can do it?
- Can you explain why your method works?
- Could someone do it with fewer tests? Are you sure? Can you explain why a solution with fewer tests is impossible?

If you get stuck try something - try anything. Put one or two balls one each side. You have to start somewhere.

- What would it mean if the scales balanced? Can you think of a second test if the first test balanced?
- What would it mean if the left (or right) side was heavier? What would your next test be?

Compare your solution and your reasons with other people. Did everyone find the same solution? Did you keep track of your ideas with a chart or a diagram?

A "decision tree" would be one way to map your plan. Write down your first test and draw a circle around it. For each test result - left, right, or balanced - draw a line to your next test. From each new test, draw a line to the following test or to your conclusion.

Play with your solution.

- How many tests would you need for six balls? How does your method change? What stays the same?
- What's the greatest number of balls you could test with two tests? Why not more?
- How many balls could you test with three tests? With four tests? Is your plan about the same?
- Is there a pattern to how many balls can be tested? Can you write a rule for how many balls can be tested with "n" tests?
- Could you write a rule for how many tests are needed for "n" balls?

We've learned something about balance scale testing. Let's get a little closer to the hard problem we started with.

Imagine there are only three balls. Two of them weigh the same amount. The other might weigh the same, or it might be a little lighter or heavier. How many tests do you need now?

Compare this to the problems we just solved? With one heavy ball out of five, there are obviously five possible solutions. But each test could only have one of three results - left, right, or balanced.

How many possible answers are there to this new problem? What are they?

Try some of your mathematician tools:

- Experiment. Make up a test. Start somewhere.
- Break it into pieces. Which of the solutions would explain a balanced result? Which would explain the left (or right) side being heavier?
- Organize. Chart or map your method.
- Generalize. How many tests would you need for four or five or "n" balls? Can you write a rule?

Are you ready for the big time?

- How many solutions are there with twelve balls if one of them might be light or heavy, or they could all weigh the same amount?
- Should three tests be enough?
- Can you suggest a possible first test?

One last question: Could you test thirteen balls - one heavy, one light, or all the same - with three tests? Why or why not?

]]>

The purpose of this exercise is absolutely not to cause everyone to solve the 12-ball problem, or worse, to show everyone the solution. The persistent, perhaps the obsessed, will solve it eventually. The exercise is rather about basic mathematical method, along with some beginning thoughts in combinatorics.

OddBall, a simple Windows program, is available for download. It allows you to select the number of balls (2 to 15), and whether the odd ball is light, heavy, or unknown. You drag balls onto the scale pans, then click the "Test" button to see the results. When you've solved the problem, drag the odd ball to the appropriate box for credit.

- OddBall.exe [44KB] - this is just the executable. If you have other VB6 programs on the system it may run correctly.
- OddBall.CAB [1.3MB] and setup.exe [1.6KB] - the CAB contains all necessary files. Download both pieces and run "setup.exe".

Students must analyze the problem in terms of separate cases. They must decide what results are possible from a given test, then focus and draw conclusions from each individual result in turn. Finally, the conclusions must be brought together to assure that all possibilities are accounted for.

The most important combinatoric result is the multiplicative effect of successive tests. While one test has three possible results (left, balanced, or right), two tests produce nine possible outcomes (left-left, left-balanced, etc.). The sequence, or combination, of tests has meaning. In fact, the balls chosen for the second test may depend on the results of the first.

Note: Although there are nine theoretical outcomes from two tests, students may recognize that four of these combinations will never actually occur.

If students can correctly determine the number of tests for a 100-ball or 1000-ball problem (with one heavy ball), that is much more important than solving the original 12-ball challenge. Likewise, the realization that the 12-ball problem presents 25 possible outcomes and is therefore potentially within reach of three tests is more important than the actual list of tests.

Keeping track of the tests will require some organized record-keeping, especially for problems with more balls. A graphic decision tree is an excellent tool. An alternative would be a decision outline, as sketched below. Only the format is different.

Sample solution to five-ball problem

- Weigh ball #1 (left) against ball #2 (right).

- If the left side is heavier, #1 is the odd ball.
- If the right side is heavier, #2 is the odd ball.
- If they balance, #1 and #2 are both normal. The odd ball must be #3, #4, or #5. I will therefore test #3 (left) against #4 (right).

- If the left side is heavier, #3 is the odd ball.
- If the right side is heaver, #4 is the odd ball.
- If they balance, #3 and #4 are both normal. Since I already know tha #1 and #2 are normal, the odd ball must be #5.

Using a solution appropriately is as important as finding it in the first place. It's in the nature of mathematics to apply solutions to similar problems and try to create more general, and therefore more powerful, rules. The multiplication of cases by successive events goes far beyond billiard balls and balance scales. But a grasp of these problems will allow an application of the rule based on understanding and not superstition.

]]>