A problem of an infinite number of balls and an urn - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-06-18T07:32:29Z http://mathoverflow.net/feeds/question/7063 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn A problem of an infinite number of balls and an urn Jean-Philippe Burelle 2009-11-28T17:01:31Z 2010-07-09T18:54:28Z <p>I think that the following problem originated in a probability textbook :</p> <p>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$.</p> <p>The question is : how many balls are left in the urn at (or after) midnight? (that is, after a countably infinite number of steps).</p> <p>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.</p> <p>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.</p> <p>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?)</p> <p>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?</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/7066#7066 Answer by Jason Dyer for A problem of an infinite number of balls and an urn Jason Dyer 2009-11-28T17:54:13Z 2009-11-29T16:06:06Z <p>The second part is the paradox of <a href="http://en.wikipedia.org/wiki/Thomson%27s%5Flamp" rel="nofollow">Thomson's lamp</a>, which can be formalized as thinking about <a href="http://en.wikipedia.org/wiki/Grandi%27s%5Fseries" rel="nofollow">Grandi's series</a> $\sum_{n=0}^{\infty}{(-1)^n}$. <a href="http://en.wikipedia.org/wiki/Summation%5Fof%5FGrandi%27s%5Fseries" rel="nofollow">This is a decent summary</a>; one can argue either "the sum is 1/2" or "there is no sum" based on the formalization used.</p> <p>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 <a href="http://plato.stanford.edu/entries/spacetime-supertasks/" rel="nofollow">generally falls under the title of "supertasks"</a>.</p> <p>To address formalizing the first part of the problem, I prefer the analogous</p> <p>$\sum_{n=0}^{\infty}{10} - \sum_{n=0}^{\infty}{1}$</p> <p>so that instead of considering the series</p> <p>1 - 1 + 1 - 1 + 1 - 1 ...</p> <p>we are thinking about</p> <p>10 - 1 + 10 - 1 + 10 - 1 ...</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/7073#7073 Answer by Kristal Cantwell for A problem of an infinite number of balls and an urn Kristal Cantwell 2009-11-28T19:55:53Z 2009-11-28T19:55:53Z <p>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:</p> <p><a href="http://en.wikipedia.org/wiki/Riemann%5Fseries%5Ftheorem" rel="nofollow">http://en.wikipedia.org/wiki/Riemann_series_theorem</a></p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/7094#7094 Answer by John Goodrick for A problem of an infinite number of balls and an urn John Goodrick 2009-11-29T00:52:53Z 2009-11-29T00:52:53Z <p>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.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/7113#7113 Answer by Theo Johnson-Freyd for A problem of an infinite number of balls and an urn Theo Johnson-Freyd 2009-11-29T07:30:25Z 2009-11-29T07:30:25Z <p>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 <em>Divergent Series</em> by Hardy.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25795#25795 Answer by Harry Altman for A problem of an infinite number of balls and an urn Harry Altman 2010-05-24T19:44:43Z 2010-05-24T21:45:10Z <p>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 &alefsym;<sub>0</sub>, 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...</p> <p>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.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25802#25802 Answer by Andrea Ferretti for A problem of an infinite number of balls and an urn Andrea Ferretti 2010-05-24T20:44:58Z 2010-05-24T20:44:58Z <p>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$.</p> <p>The question is: if we extend this function as a "function" from ordinals to say <code>$\mathbb{N} \cup \{ \infty \}$</code> 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.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25816#25816 Answer by fedja for A problem of an infinite number of balls and an urn fedja 2010-05-24T23:11:34Z 2010-05-24T23:11:34Z <p>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! </p> <p>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. </p> <p>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. </p> <p>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". </p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25830#25830 Answer by Joel David Hamkins for A problem of an infinite number of balls and an urn Joel David Hamkins 2010-05-25T00:43:28Z 2010-05-25T00:43:28Z <p>You are describing what is known as a <a href="http://en.wikipedia.org/wiki/Supertask" rel="nofollow">supertask</a>, 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 <a href="http://mathoverflow.net/questions/22038" rel="nofollow">deal with the Devil</a>, which is similar to your example. Let me mention a few additional examples here.</p> <p>In the article <em>"A beautiful supertask"</em> (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:</p> <ul> <li>Even though each step of the physical system is energy-conserving, the system as a whole is not energy-conserving in time.</li> </ul> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25845#25845 Answer by Mark for A problem of an infinite number of balls and an urn Mark 2010-05-25T05:19:41Z 2010-05-25T05:19:41Z <p>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. </p> <p>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.</p> <p>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 <strong>all</strong> balls have been removed there are <strong>none</strong> left" is a tautology.</p> <p>With the two answers contradicting each other it seems to me that either: the way we deal with unbounded sequences is wrong, or my <strong>all</strong> vs <strong>none</strong> 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.</p> <p>Some additional ways to think about the problem to muddy the waters further: </p> <p>"How long is ball $n$ in the urn before it is removed?" </p> <p>and the followup question</p> <p>"What is the average length of time each ball is in the urn?"</p> <p>"If you can't/won't/don't read the labels why <strong>isn't</strong> this equivalent to throwing 9 balls in the urn at $\frac{1}{2^n}$ before midnight for each $n\in\mathbb{N}$?"</p> <p>and the followup</p> <p>"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}$?"</p> http://mathoverflow.net/questions/7063/a-problem-of-an-infinite-number-of-balls-and-an-urn/25910#25910 Answer by Daniel Asimov for A problem of an infinite number of balls and an urn Daniel Asimov 2010-05-25T17:57:48Z 2010-05-25T17:57:48Z <p>The reason this problem has the generally accepted answer of 0 balls in the jug at midnight -- among <em>mathematicians</em> -- 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.</p> <p>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.</p> <p>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 <em>Mathematical Games</em> column in <em>Scientific American</em>, where "zero balls at midnight" was given as the correct solution. (See <em>A Mathematician's Miscellany</em>, J.E. Littlewood, Methuen, 1953.)</p> <p>Philosophers, on the other hand, are still debating this problem. (See, for example, <em>Paradoxes from A to Z</em> by Michael Clark, 2nd ed., Routledge, 2007.)</p>