A problem of an infinite number of balls and an urn

Question

I think that the following problem originated in a probability textbook :

You have a countably infinite supply of numbered balls at your disposal. They are all labeled with the natural numbers {1,2,3,...}. At 11h30, you put in the urn the balls labeled 1 to 10, and then right after remove the ball labeled 1. Then, at 11h45, you put into the jug balls 11 to 20, and remove the ball number 2, etc. In general at $\frac{1}{(2^n)}$ hours before midnight, you put in balls $(n-1)10+1$ to $10n$, and remove the ball labeled $n$.

The question is : how many balls are left in the urn at (or after) midnight? (that is, after a countably infinite number of steps).

I know that the most accepted answer to this question is that at midnight there aren't any balls left in the urn, because if you consider ball $n$, you know that it has been removed from the urn $\frac{1}{(2^n)}$ hours before midnight, and hasn't been put back at any subsequent step. Thus there can't be any balls in the urn at midnight.

I know that the fact that this problem is very counter-intuitive is probably that it is not worded in any particular axiomatic system, so you can have multiple interpretations of the answer. I know that the above reasoning implies that after midnight, there can't be any balls in the urn that have a natural number of them, and I also know that there are only balls with natural numbered labels available, so that would imply that the jug is empty, but it still is not that much convincing.

consider the following different problem : At the start, there is one ball in the jug labeled 1. Then, at the first step, you remove ball 1 and put in ball 2 at the same time. Then, you remove ball 2 and put in ball 3, etc... There is a ball in the jug at any time, so certainly there should still be ball in the urn at midnight, but it can't have a natural-numbered label. Consider also the following : in the previous problem, after removing ball #2 at the second step, but back in ball #1. Then at the next step remove ball 1 and put in ball 2, etc. At midnight there is no way to know if the ball is labeled 1 or 2. (probably because the limit of the series $(-1)^n$ doesn't exist?)

My question is : Is there any more satisfying way to formalize this problem, or to explain it that would resolve the paradox that the number of balls in the jug gets constantly larger, never diminishes, and that at the end there is nothing left in the urn?

Answer 1

A good way to formalize the problem is to describe the state of the jug not as a set (a subset of N), because those are hard to take limits of, but as its characteristic function. The first "paradox" is that pointwise limits are not the same as uniform limits. Later ones can be "resolved" by extending the notion of "limit" in various ways, most of which were invented by Euler. See for example the book Divergent Series by Hardy.

Answer 2

You are describing what is known as a supertask, or task involving infinitely many steps, and there are numerous interesting examples. In a previous MO answer, for example, I described an entertaining example about the deal with the Devil, which is similar to your example. Let me mention a few additional examples here.

In the article "A beautiful supertask" (Mind, 105(417):81-84, 1996), the author Laraudogoitia considers the situation with Newtonian physics in which there are infinitely many billiard balls, getting progressively smaller, with the $n^{th}$ ball positioned at $\frac1n$, converging to $0$. Now, set ball $1$ in motion, which hits ball 2 in such a way that all energy is transferred to ball 2, which hits ball 3 and so on. All collisions take place in finite time, because of the positions of the balls, and so the motion disappears into the origin; in finite time after the collisions are completed, all the balls are stationary. Thus:

• Even though each step of the physical system is energy-conserving, the system as a whole is not energy-conserving in time.

The general conclusion is that one cannot expect to prove the principle of conservation of energy throughout time without completeness assumptions about the nature of time, space and spacetime.

A similar example has the balls spaced out to infinity, and this time the collisions are arranged so that the balls move faster and faster out to infinity (using Newtonian physics), completing their progressively rapid interactions in finite total time. In this case, once again, a physical system that is energy-preserving at each step does not seem to be energy-preserving throughout time, and the energy seems to have leaked away out to infinity. The interesting thing about this example is that one can imagine running it in reverse, in effect gaining energy from infinity, where the balls suddenly start moving towards us from infinity, without any apparent violation of energy-conservation in any one interaction.

Another example uses relativistic physics. Suppose that you want to solve an existential number-theoretic question, of the form $\exists n\varphi(n)$. In general, such statements are verified by a single numerical example, and there is in principle no way of getting a yes-no answer to such questions in finite time. The thing to do is to get into a rocket ship and fly around the earth, while your graduate student---and her graduate students, and so on in perpetuity---search for an additional example, with the agreement that if an example is ever found, then a signal will be sent up to your rocket. Meanwhile, you should accelerate unboundedly close to the speed of light, in such a way that because of relativistic time contraction, the eternity on earth corresponds to only a finite time on the rocket. In this way, one will know the answer is finite time. With rockets flying around rockets, one can in principle learn the answer to any arithmetic statement in finite time. There are, of course, numerous issues with this story, beginning with the fact that unbounded energy is required for the required time foreshortening, but nevertheless Malament-Hogarth spacetimes can be constructed to avoid these issues, and allow a single observer to have access to an infinite time history of another individual.

These examples speak to an intriguing possible argument against the Church-Turing thesis, based on the idea that there may be unrealized computational power arising from the fact that we live in a quantum-mechanical relativistic world.

Answer 3

The second part is the paradox of Thomson's lamp, which can be formalized as thinking about Grandi's series $\sum_{n=0}^{\infty}{(-1)^n}$. This is a decent summary; one can argue either "the sum is 1/2" or "there is no sum" based on the formalization used.

For some philosophers, this is a good illustration that the operation above does not occur in real life (which is not necessarily irrelevant, since it affects which models of space and time are valid). The research generally falls under the title of "supertasks".

To address formalizing the first part of the problem, I prefer the analogous

$\sum_{n=0}^{\infty}{10} - \sum_{n=0}^{\infty}{1}$

so that instead of considering the series

1 - 1 + 1 - 1 + 1 - 1 ...

we are thinking about

10 - 1 + 10 - 1 + 10 - 1 ...

although there are certainly other ways. One can try to obtain the continuation of the function $f(1-\frac{1}{2^n})=9n$ from [0,1] using the Alexandroff compactification of the real numbers. This gives the answer of "infinite", although I'm not keen on this formalization because it removes the iterative sense of the original problem.

I find such paradoxes to be most useful (to mathematicians) pedagogically, because it allows students to apply their mathematical intuition and give them some investment before formalizing their handling of infinity.

Answer 4

This procedure is very common in mathematics in general, especially in inductive constructions. Usually one doesn't scream "paradox!" when seeing a function on the set of positive integers defined recursively by, say, $f(1)=1$, $f(a)=f([a/2])+1$. But let's think of it this way. We have a machine that computes the values. After each computation, we put the values that can be computed next in a queue. At the first step we know $f$ only at $1$ so the queue consists of 2 and 3. After we serve 2, the queue becomes 3,4,5. After we serve 3, it becomes 4,5,6,7, and so on. What a horror: the more numbers we've served, the longer the queue becomes, so in the end we'll, probably, have infinitely many numbers that still need to be computed!

It is very funny how one easily swallows such things when they aren't singled out from long arguments and how one finds them "paradoxical" and "unbelievable" when they are presented in their pure form.

As to "occurring in the real life", just restate the Zeno's paradox as "After you reach the middle of the way, you'll still need to reach 5/8, 6/8 and 7/8 of the way. After you reach the 5/8 mark, you'll need to reach 41/64, 42/64, ... , 63/64. And so on. In this version, the conclusion is that not only will you never reach the end, but it'll be farther and farther away from you with each step.

I wonder how many people realize that this might be one of the things the Red Queen meant when she told Alice, "“Now, here, you see, it takes all the running you can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!"

Answer 5

You can formalize this problem by talking about limits of sets, where the limsup of a sequence of sets consists of the elements that are in infinitely many of them, and liminf consists of the elements that are in cofinitely many of them, and the limit exists if these are equal. In this case, if we look at the sets of balls in the urn at each time, we see that the limit of this sequence is the empty set. Of course, as you point out, in the case where you keep putting in 10, the limit of the cardinalities is $\aleph_0$, and in the case of taking 1 out, it doesn't exist. So I think what we get out of this really is the conclusion that taking cardinalities is a discontinuous operation...

Edit: I just realized, it would probably help to clarify if you're unfamiliar - the reason the above are sensible notions of limsup and liminf is because they're $\bigcap_{n\in\mathbb{N}} \bigcup_{k=n}^\infty A_k$ and $\bigcup_{n\in\mathbb{N}} \bigcap_{k=n}^\infty A_k$, respectively.

Answer 6

There is a paradox involving the series 1-1+1-... the terms can be grouped in pairs each pair summing to zero (1-1)+(1-1) or there is the following regrouping 1+(1+1) -1 +(1+1=1+1)-(1+1)... which each pair of series following +2^k ones minus 2^k-1 ones starting at k=3 and continuing to infinity. This grouping will produce the same pattern as those in your problem. This involves regrouping an infinite series to change values. This is related to Riemann series theorem that if an infinite series is conditionally convergent, then its terms can be arranged so that the series converges to any given value, or diverges. see the following for more information:

https://en.wikipedia.org/wiki/Riemann_series_theorem

Answer 7

I'm just rephrasing what other people have said, but more or less you are telling us this. You have function $f$, defined on $\mathbb{N}$ which is the number of balls after $n$ steps. One can actually compute $f(n) = 9n$.

The question is: if we extend this function as a "function" from ordinals to say $\mathbb{N} \cup \{ \infty \}$ what is the value of $f(\omega)$? You are arguing that is should be $\infty$ and indeed it is if you require some sort of continuity of $f$ at $\omega$. But you have just shown a (discontinuous) extension with $f(\omega) = 0$. There is nothing paradoxical about it.

Answer 8

For me, one reason why the accepted answer to the original problem is somewhat "less than satisfying" is that it answers the stated question by rephrasing into a supposedly equivalent question. "How many balls are left at midnight?" Changes to "Can I remove each ball before midnight?" Our experience with completing finitely many steps in long (i.e. not infinitesimal) lengths of time tells us these two questions are the same... But I don't think they are.

After all our prior experience with series and sequences tells us how to answer the first, by taking a limit. At any time before midnight we know how many balls are in the urn, from $\frac{1}{2^n}$ before midnight until $\frac{1}{2^{n+1}}$ before midnight we have $9n$ balls. For any number of balls $M$ we can find a time $T=$ ($\frac{1}{2^n}$ for some $n$) where for all times $t\geq T$ (before midnight) we have $9n>M$ balls in the urn. i.e. as we approach midnight the number of balls is unbounded.

We also know how to answer the second phrasing of the question. "Yes, we can remove all the balls before midnight" By the aforementioned name the ball I'll tell you when it left method. At this point I think that "When all balls have been removed there are none left" is a tautology.

With the two answers contradicting each other it seems to me that either: the way we deal with unbounded sequences is wrong, or my all vs none tautology is not actually a tautology, or those two phrases we assume are the same... are not. Unless someone sees another possibility beyond these three I have to think that it is the third option that we must pick.

Some additional ways to think about the problem to muddy the waters further:

"How long is ball $n$ in the urn before it is removed?"

and the followup question

"What is the average length of time each ball is in the urn?"

"If you can't/won't/don't read the labels why isn't this equivalent to throwing 9 balls in the urn at $\frac{1}{2^n}$ before midnight for each $n\in\mathbb{N}$?"

and the followup

"If, instead of placing the removed ball in different spot, you place the "non-read label ball" back into the countably infinite supply is this now equivalent to throwing in 9 balls at each each $\frac{1}{2^n}$?"

Answer 9

The reason this problem has the generally accepted answer of 0 balls in the jug at midnight -- among mathematicians -- is that for any given ball, one may follow its itinerary: at some point it goes into the jug, and then at some point no earlier it leaves the jug, never to be moved again.

Thus it would be easy to formalize a generalized class of problems so that one may prove rigorously that as long as each ball n is moved only finitely many times before midnight, it is at midnight where its last motion took it to.

The infinitely-many-marbles problem was probably created by the mathematician J.E. Littlewood in the early 1950s, and was popularized in Martin Gardner's Mathematical Games column in Scientific American, where "zero balls at midnight" was given as the correct solution. (See A Mathematician's Miscellany, J.E. Littlewood, Methuen, 1953.)

Philosophers, on the other hand, are still debating this problem. (See, for example, Paradoxes from A to Z by Michael Clark, 2nd ed., Routledge, 2007.)

Answer 10

Thinking about these kinds of problems has convinced me that it may be quite reasonable to assume that there's an absolute bound on how fast an object can travel. Or at least, that this is more "intuitive" than the alternative.

Answer 11

I am currently working on the theory of divergent integrals and series, so I will try to look at your problem from this point of view (see also discussion at this answer).

One thing that should be mentioned here is that the answer to your question depends on the time intervals between the steps and on the time interval you take as a unit. So I will not talk about hours but just about units of time.

Let first consider a simplified problem that has much simpler solution. Suppose each step you add 9 balls, just like in your question, but the steps are separated by equal intervals. You start at time $0$. What number of balls there will be in the urn after infinite time?

The solution is quite simple: $$\sum_{k=0}^\infty 9=9\sum_{k=0}^\infty1$$

The last divergent sum has a special symbol in the linked theory, $\omega_+$. Thus, the answer is $9 \omega_+$. Since $\omega_+$ has regularized value of $1/2$, the answer has the regularized value $9/2$ (in case you are interested in the regularized solution).

Now, what happens if you add the balls after diminishing time intervals? Suppose you start one time unit before the singularity point and add 9 balls after intervals that become twice shorter each step.

The final sum will also belong to the same set of divergent integrals and series as the previous solution.

Consider the curve $-1/x$. It has a property that its integrals over exponentially diminishing intervals are the same. For instance, $\int_{-1}^{-1/2}-1/xdx=\ln2$, $\int_{-1/2}^{-1/4}-1/xdx=\ln2$, $\int_{-1/4}^{-1/8}-1/xdx=\ln2$ etc. Thus the integral of this curve from $-1$ to $0$ can represent the solution to our problem (we would have to divide it by $\ln 2$ and multiply by $9$ so to account for the number of balls).

There is one more problem. The graphics of the curve on all intervals are not symmetric, so, unfortunately, this may affect the regularized part and needs additional analysis.

Now, I have a solid result that $\int_1^\infty 1/x dx=\ln \omega_+ + \gamma$. The $\ln \omega_+$ has the regularized value $-\gamma$, so the whole integral has regularized value $0$. If we conjecture, based on the properties of logarithm that $\int_0^1 1/xdx$ is equal, the conjectured solution to our problem turns out to be $$\frac{9(\ln\omega_++\gamma)}{\ln 2}+r$$ This $r$ represents the regularized value of the solution but to find it we should examine the bricked version of $1/x$ rather than smooth one (so that on each interval the function to be symmetric against the middle of the interval), for which I do not have a technique.

I remind that in the second variant of the problem we made some conjectures which are more intuitive than solid.