Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as no longer relevant by Robin Chapman, François G. Dorais Jul 9 '10 at 19:34

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I think the real answer is that the problem gives no information about what happens at midnight or later. Maybe at exactly midnight a jaguar comes along and eats all but 8 of the balls. –  Reid Barton Nov 28 '09 at 17:13
I assume that there is a typo: at 11:45 you put in balls 11 to 20. You can't put in ball 10 as it is already in. A somewhat different typo in in the "In general..." next sentence. I assume that you mean to put in the balls numbered (n-1)*10 + 1 to n*10? –  Sam Nead Nov 29 '09 at 18:23
This is how I justify buying mathematics books faster than I can read them. If I live forever, even though I keep buying them, I'll eventually read each one. –  Dan Piponi May 24 '10 at 21:02
Can you, please, change "infinite balls" to $\textit{infinitely many}$ balls in the title? Infinite balls have something unsavory about them. –  Victor Protsak May 25 '10 at 4:56
Write about balls and jugs ... someone may think you intend some sexual double-entendre... Isn't that mathematical item you put the balls in usually known as an urn? –  Gerald Edgar May 25 '10 at 12:22

10 Answers 10

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.

share|improve this answer

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 intutition and give them some investment before formalizing their handling of infinity.

share|improve this answer
This is a good answer for the last of the situations I posted, but what about the original question? The one where you add more balls than you remove? –  Jean-Philippe Burelle Nov 28 '09 at 19:40
Hm, somehow I thought the second question was the only actual one. I have edited. Let me know if you need more. –  Jason Dyer Nov 29 '09 at 14:44

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 disappers 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.

share|improve this answer
Joel, this is so cool! I know you did work on infinite time Turing machines -- In the literature, are there any discussions of infinite time Turing machines which go into serious detail w.r.t. the physics you mention? –  Grant Olney Passmore May 25 '10 at 17:32
Yes, Philip Welch has done some nice work on it. Look at a few of his recent papers on his web page: maths.bris.ac.uk/~mapdw One paper is explicitly concerned with physical models for infinitary computability. –  Joel David Hamkins May 25 '10 at 17:52
IIRC if you have access to unbounded energy or precision, you can tackle NP-complete problems in polytime with analog computers. –  Steve Huntsman Jul 10 '10 at 11:31

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 "occuring 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 black Queen meant when she told Alice that "Here you need to run as fast as you can just to stay where you are and if you want to get anywere else, you need to run twice faster".

share|improve this answer

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:


share|improve this answer

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.

share|improve this answer

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 ℵ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 discontinous 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.

share|improve this answer
Yeah, I think this is the key. If you think in measure theoretic terms, you could say that integration is not continuous with respect to the topology of pointwise convergence (though it is lower semicontinuous, which is Fatou's lemma). In particular, it is not necessarily true that $\liminf \mu(A_n) = \mu(\liminf A_n)$, though $\ge$ does hold. (For this example, $\mu$ could be counting measure.) So I think this paradox is just the human tendency to assume that "simple" operations are continuous. –  Nate Eldredge May 25 '10 at 19:20

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}$?"

share|improve this answer

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 (discontinous) extension with $f(\omega) = 0$. There is nothing paradoxical about it.

share|improve this answer

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.)

share|improve this answer
I am a mathematician and I don't accept "0 balls" as "the" answer (because of implicit continuity assumptions). There is ample evidence at this page that I am not alone in that. –  Victor Protsak May 26 '10 at 4:48
Naturally, not everyone will agree on a philosophical issue. Which is why I said Martin Gardner's solution is "generally accepted," not "universally accepted," among mathematicians. –  Daniel Asimov May 30 '10 at 0:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.