Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a computer scientist by training, but have a fair amount of math background that I've picked up through classes, teaching, and general interest.

A student of mine posed a question to me. I think that the answer I gave is correct, but I'd like to double-check my understanding to make sure that what I said was correct.

The problem concerns the following puzzle:

You have infinitely many balls numbered $0, 1, 2, 3, ...,$ etc. At time $0$, you put balls $0, 1, 2, 3, ..., 9$ into a well. At time $\frac{1}{2}$, you remove ball $0$ from the well and add balls $10, 11, 12, 13, ... 19$ into the well. At time $\frac{3}{4}$, you remove ball $1$ from the well and put balls $20, 21, 22, 23, ..., 29$ into the well.

More generally, at time $1 - \frac{1}{2^n}$, you place balls $10n, 10n + 1, 10n + 2, ..., 10n + 9$ into the well and remove ball $n - 1$.

How many balls will be in the well at time 1?

The student mentioned that they were confused by the problem because they had two equally good explanations for what was going on that seemed contradictory:

  1. Notice that every ball that is added into the well is at some point removed from the well. Therefore, at time $1$, after the process finishes, all balls will have been removed, so there are no balls left in the well.

  2. At every step, the number of balls in the well is increasing. Therefore, at time $1$, after the process finishes, there will be infinitely many balls in the well.

My reply to the student is that, as stated, there is no way to answer the question because the problem is underspecified. Specifically, I thought that the process, as described, does not give enough information to determine what happens at time $1$.

More precisely - we can model the balls in the well after each step of the process by writing out a series of sets $S_n$ that say which balls are in the well after $n$ steps. It's given by the recurrence

$$S_0 = \{0, 1, 2, ..., 9\}$$

$$S_{n+1} = (S_n \cup \{10n + 10, 10n + 11, 10n + 12, ..., 10n + 19\}) - \{n\}$$

The question the student wants the answer to is, essentially, equivalent to asking what $S_\omega$ (that is, the set corresponding to the elements in the well after all of the steps have finished) is given the values of $S_0, S_1, S_2, ...$. However, just given the information above, there's not enough information to determine what $S_\omega$ is. It's perfectly consistent to think that $S_\omega = \emptyset$ or that $S_\omega = \mathbb{N}$.

I then went on to explain that we could try to define what $S_\omega$ "ought" to be by trying to find some reasonable definition of the limit of this process, but that anything we'd come up with would just be us arbitrarily choosing some definition of a limit that we think behaves nicely and correctly models what "should" happen after everything finishes.

The student then gave me a follow-up question: well then, let's consider a different process. Suppose at time 0, you add ball 0 to the well. At time $\frac{1}{2}$, you add ball $1$ to the well. At time $\frac{3}{4}$, you add ball $2$ to the well. At time $\frac{7}{8}$, you add ball $3$ to the well. What balls are in the well at time $1$ this time?

My reply to this question was the same as before - given just what you have described here, there isn't enough information to answer the question. However, I said, in this particular case there is a reasonable definition of a limit that we could use (specifically, since the set of balls in the well at time $t$ is always a subset of the balls in the well at time $t + \epsilon$ for any $\epsilon > 0$), we could define the limit of the process to be the union of all of those sets, resulting in all infinitely many balls being in the well at time $1$. However, that's just the limit of the process - just given the process described, it's not clear that it actually converges to this limit - but we can arbitrary define the set of balls in the well at time $1$ to be this limit.

My questions are the following:

  1. Is my analysis of the question and my reply technically correct? That is, am I technically correct in claiming that the problem is underspecified?

  2. Is my analysis of the question and my reply reasonable? That is, is there some existing mathematical framework that this problem falls into such that there is an answer the mathematical community would agree on as correct?

Thanks!

share|improve this question
1  
1  
@Martín-BlasPérezPinilla Oh wow - apparently this has a name: it's the Ross-Littlewood paradox. I had no idea! –  templatetypedef Feb 1 at 22:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.