The Balls of Death

Question

You have nightmares about a pool ball with the number 1 on it, and an empty box. Why?

Immortality

Imagine, if you will, we are 5000 years into the future. Medicine has evolved and we now are immortal - with one exception, you can be executed and put to death.

Time's Changed

Times are much different in 7020. Everyone is required daily to play a game. This game is a matter of life or death.

The Game

The game is simple. You choose a pool ball from a box. You then have that ball replaced with other balls with a number lower than the one you chose. If you choose a 1, however, you can't replace it. If the box ends up empty, you die. [Classic Game Dating Back early 1900's]

The Rules

Each pool ball in the box has a number on it ( a positive integer) and there is an infinite supply. That means there are an infinite number of pool balls with the number 50 on it, as there are with an infinite number of balls with the number 1000 on it.

In a particular game box there are finitely many of these balls, but the box has infinite capacity - it can continue being filled with no limitations.

Each day you are required to choose a ball, discard it, and replace that ball in the box with any number of lower numbered balls. As many as you want. If you choose ball number 44, you can replace it with a million balls with 43 on it. Or a billion. Whatever. Your choice.

If you choose a ball with a 1 on it, you can't replace it with anything. Lost your turn, sort of. It still gets discarded, though.

If the box ever empties, you are executed.

You might as well keep a record of chosen numbers, this will probably be a long game. :)

Game Over?

What is your strategy by which you never get executed, or is death inevitable sooner or later? Please explain your answer.

Answer 1

This is a famous problem.

You will be executed in finitely many days.

This can be easily

proved by induction on the maximal number in the box

as follows:

If the maximal number in the box is $1$, then everyday you just pick a ball and discard it, so after finitely many days, you will be executed.

Now

suppose we have shown that, if the maximal number is less than $d$, then you will run out of balls in finitely many days.

Then

if the maximal number is equal to $d$, then by what we have shown, you will have to use one ball with number $d$ in finitely many days, otherwise you may survive with the other balls forever, contradicting our previous result.

And

this being repeated several times, you will eventually run out of balls with number $d$, and doomed to die in finitely many days.

Answer 2

You

are definitely going to die.

The highbrow way to see it:

if you have $a_k$ balls with the number $k$ then consider the ordinal $\sum a_k\omega^k$ which clearly decreases at every step; the ordinals are well-ordered and we're done.

Without requiring so much fanciness:

Whatever is in your box, I claim that there will, after finitely many steps, come a time when the smallest number in the box decreases. This is obviously true if there is only one ball in the box. If it isn't always true, then let's take a box with as few balls as possible for which it's false. So, we're supposing that the current state of the box is such that (1) you can go on for ever without reducing the smallest-number-in-the-box, but (2) if you have any box with fewer balls, you can't. We'll quickly see that this leads to an impossibility; so there can't be any such box; and the only way that can be so is if there's no box for which you can go on for ever.

So:

with the current state of the box, you can go on for ever without reducing the smallest number. This means in particular that you can go on for ever without ever touching the ball in the box whose number is smallest. (Or, if there are multiple such balls with the same number, any of them.) That means that you could simply remove that ball and go on for ever. But that's impossible, because we already supposed that your box had as few balls as possible allowing you to go on for ever.

And now

note that the smallest number in your box can't go on decreasing for ever.