It is $10$ o'clock, and I have a box.
Inside the box is a ball marked $1$.
At $10$:$30$, I will remove the ball marked $1$, and add two balls, labeled $2$ and $3$.
At $10$:$45$, I will remove the balls labeled $2$ and $3$, and add $4$ balls, marked $4$, $5$, $6$, and $7$.
$7.5$ minutes before $11$, I will remove the balls labeled $4$, $5$, and $6$, and add $8$ balls, labeled $8$, $9$, $10$, $11$, $12$, $13$, $14$, and $15$.
This pattern continues.
Each time I reach the halfway point between my previous action and $11$ o'clock, I add some balls, and remove some other balls. Each time I remove one more ball than I removed last time, but add twice as many balls as I added last time.
The result is that as it gets closer and closer to $11$, the number of balls in the box continues to increase. Yet every ball that I put in was eventually removed.
So just how many balls will be in the box when the clock strikes $11$?
$0$, or infinitely many?
What's going on here?
Answer
[Edit.] I am editing my answer to try to give some more insight, prompted by comments on my original response. I hope to develop a deeper idea into what's going on here.
The short answer is that what is important is not the size of the set of balls at any particular time, but rather how the set of balls changes; and ultimately what the limit of those sets are. The key is to determine what that limit is, and then determine how many balls are in that limiting set. The answer is that the limit is the empty set, which has size 0. The rest of this answer is devoted to describing this in some detail.
Part of what I have added to my answer is to point out that although there are multiple ways of measuring convergence — in terms of various norms on characteristic functions — only one of these actually defines the limit of the sequence, and in this case the limit is well-defined.
What matters is not the number of balls, but the set of balls
In this problem, we have more than just a number of balls which changes with time. What's different is that each of these balls has a unique identity.
This might not seem like it should matter, but it means that the state of the "system" is not a quantity of balls but a set of balls. That set has a certain size, but the size is a derived feature of the system; it follows from which particular set of balls is present. So it is important to determine what the limit of the sequence of sets is.
Description of the problem in terms of sets
Let's consider how the set of balls in the box change with time in the game you present. At step $n$, you add $2^n$ balls, and remove the $n$ lowest-numbered balls. The "state of the system" is given by the following sets:
$S(0) = \{1\}$
$S(1) = \{2,3\}$
$S(2) = \{4,5,6,7\}$
$S(3) = \{7,8,9,10,11,12,13,14,15\}$
$S(4) = \{11,12,\dots,31\}$
etc.
Note that after step 1, the first ball is removed, never to be added again; so it is not an element of the final set. Similarly, at step 2, the second and third balls are removed, never to be added again; so they aren't elements of the final set. And so on. So... none of the balls are in the final set. So then it must be empty! It doesn't matter that the number of balls in the sequence are increasing; what matters is that the number of balls which will never again be in the box is also increasing, and in the limit includes all of the balls.
We can make this more striking by considering, for each step $n$, the set of balls $I(n)$ which is in the set $S(t)$ for all $t \geq n$: that is, $I(n) = S(n) \cap S(n+1) \cap S(n+2) \cap \dots $. Because each ball is eventually removed, never to be added again; this means that
$I(0) = I(1) = I(2) = \dots = \varnothing$
So while the original description makes it look like, moment-to-moment, the final state of the box should be to hold infinitely many balls, a more "forward looking" approach shows that it's clear that the final state of the box is to be empty.
An analysis in terms of characteristic functions
We can contrast the "intuitive" answer of infinitely many balls in the box, and the more precise answer that there ultimately are no balls in the box, using characteristic functions: that is, we replace each set $S(n)$ by a function $f_n : \mathbb{N} \to \{ 0, 1\}$ which is $1$ for those integers belonging to $S(n)$, and $0$ otherwise.
Consider the various $p$-norms on these functions. The cardinality of each set $S(n)$ is precisely equal to the $1$-norm of the function $f_n$ , which grows without bound. The fact that the 1-norm grows without bound — and in particular, the distance between the function $f_n$ and the zero function $\mathbf{0}$ in the $1$-norm grows without bound — is essentially the source of most people's intuition about this problem, and exactly the reason why they find it counterintuitive that the final set should be empty.
But just as the size of a set is a derived quantity, the norm of a function — or of a sequence of functions — is also a derived quantity; and the norm of the limit of a sequence of functions is not necessarily the limit of the norms. In fact, the functions $f_n$ don't converge to anything, in any of the p-norms; it simply diverges to nothing in particular.
But there is at least one notion of convergence which applies to the functions $f_n$, and that is point-wise convergence — the form of convergence which is the broadest, in the sense that it applies to the most cases (and with which all other notions of convergence must agree, if they show that a sequence of functions converges at all). We may simply show that for each $x$, we have $f_n (x) = 0$ for sufficiently large n. It then follows that the sequence $f_n$ converges to $\mathbf{0}$.
The fact that the sequence $f_n$ doesn't converge to $\mathbf{0}$ under any of the p-norms doesn't matter; ultimately what matters is that the sequence converges point-wise, because what we're interested in is the cardinality of the limit itself, which is defined in terms of point-wise convergence. At worst, from a certain aesthetic point of view, one might say that it doesn't converge particularly gracefully (informally speaking) to $\mathbf{0}$; but it does indeed converge, and that is all that matters.
So: using characteristic functions, which is ultimately equivalent to the sets described in the first place, one can show that the sequence of sets does converge, and what they converge to is the empty set. But take comfort that your intuition that they should not reflects a certain awareness of the concept of $p$-norms. :-)
No comments:
Post a Comment