Friday, January 25, 2008

The infinite bag of billiards balls

Difficulty: 5 of 10

This is a classic puzzle that often provokes lively discussion among puzzling communities.

We start with an empty bag at 11:00. We put in 10 billiards balls, which are numbered 1 through 10. But then we take out the ball labeled #1. At 11:30, we add 10 more billiards balls, which are numbered 11 through 20, and remove the ball labeled #2. At 11:45, we add balls 21 through 30 and remove #3.

This process is repeated infinitely. At each step, the next ten billiards balls are put into the bag, and the lowest number in the bag is removed. There are an infinite number of steps before 12:00, since the time between each step decreases at each step.

Obviously this puzzle is meant to be abstract, as you cannot actually perform an infinite number of steps within an hour, nor can a bag actually hold that many billiards balls. But we can still ask a genuine mathematical question about the situation: what's left in the bag after 12:00?

Variation 1:
Instead of removing the lowest numbered ball in the bag at each step, we instead remove the highest numbered ball. So on step 1, we remove #10, on step 2, we remove #20, and so forth. What's left in the bag after 12:00?

Variation 2:
On the first step, we add only billiards balls labeled 1 through 9. Instead of adding #10, we just take #1 and paint an extra zero at the end. On the second step, we add numbers 11 through 19, and add an extra zero to the end of #2, resulting in #20. On the third step, we add numbers 21 through 29, and add an extra zero to the end of #3. This process is repeated infinitely before 12:00. What's left in the bag after 12:00?

Solution

2 comments:

Anonymous said...

When you say, "What is left," do you mean, what numbers are left? or how many billiard balls are left? And if it's how many, wouldn't it just be "9n" where n=infinity? I think I must have missed something, misunderstood the problem, or you just didn't explain it well enough : P

miller said...

Which billiards balls are left in the bag? Identify the set of numbers that are in the bag.

It is important to remember that the puzzle asks about what is left after an infinite number of steps. Just because there are 9n balls left after the nth step does not mean that this is still true after an infinite number of steps.

For example, I can say that at the nth step, there is always a finite number of balls in the bag. But this is not necessarily remain true after an infinite number of steps.