A strange puzzle having two possible solutions

Question

A friend of mine asked me the following question:

Suppose you have a basket in which there is a coin. The coin is marked with the number one. At noon less one minute, someone takes the coin number one and put into the basket two coins: the number two and the number three. At noon less $\frac{1}{2}$ minute, he takes the coin number two and put into the basket the coins number $4$ and the number $5$ and so on. At noon less $\frac{1}{k}$ he takes the coin number $k$ and put two other coins.

The question is: How many coins I can find in the basket at noon?

Intuitively the answer is $\infty$ because I added one coin for infinite times. But the correct answer seems to be $0$ because every coin numbered $k$ has been removed at noon less $\frac{1}{k}$ of minute. What is the correct answer? Thanks.

Answer 1

The reason your intuition deceives you is because we often like to forget strategies which depend on the numbering of the coins, and instead think about it in terms of abstract coins, so at each step the devil takes back one coin, and puts in two new ones instead.

The problem is that this description of the problem has different possible outcomes, which depend on the devil, and how much he likes you. Your friend suggests the first case, of a Scrooge McDuck sort of devil. But to understand the difficulty in accepting the solution, let's consider the three cases.

Case I: The cheapskate devil.

The devil has a list of all the coins. At the $k$-th step he removes the coin with the least index which is still in the basket, and puts in the two coins with least indices he haven't used yet. You can see now, that each coin finds itself with the minimal index at some point, so each coin gets removed. And we are left with nothing.

Case II: The compassionate devil.

This devil wants you to be able to afford a cold beer, after suffering through this confusing process. So he decides to leave you with $n$ coins. He lists the coins, and by the $n$-th level he used the first $k$ coins, and now he repeats the previous strategy. Take out the coins with least possible index $>k$, and add two more. At the end, there cannot be any coin of index $>k$ (the same argument as before), but from the first $k$ coins we have exactly $n$ left.

Case III: The benevolent devil.

We start with the basket having the coin indexed as $1$. At each step the devil removes a coin with an odd index, and puts in two coins, one with an odd index and one with an even index. Since no even indexed coin was ever removed, the basket contains an infinite amount of coins.

You can see this is a legal strategy, because at each step he adds a coin with an odd index, to be taken out the next time.

---

To conclude, this shows that there is really no clear "intuitive" answer to this process, and it depends on the strategy for removing coins. So one cannot really be sure what is the endgame without carefully analyzing that strategy.

(As often happens with infinite things in mathematics...)

Of course, your friend plainly gave the first strategy, so if you follow the mathematics you will see why you'll be left with nothing at all.

Answer 2

Let us formalize:

The Analytic approach

Let $C_m$ be the number of coins at time $\frac1m$ (after the exchange). Then $$C_m = \sum_{n=1}^m 2_{\text{added}} - 1_{\text{removed}} = \sum_{n=1}^m 1 = m$$ The number of coins in the basket at time $t\in [-\frac1n, -\frac1{n+1})$ is simply $n$. $$\mathrm{COINS}(t) = \left\lceil \frac1{-t} \right\rceil, \qquad t\in[-1,0)$$
Seeking the value for $m\to\infty$ is the same as taking either $\lim_{t\nearrow 0} \mathrm{COINS}(t)$ or $\lim_{m\to\infty} C_m$ both evaluate to $\infty$.

Now asking for $\mathrm{COINS}(0)$ is a completely different matter, since $\mathrm{COINS}$ is not at all continuous in $0$ and therefor the value at $0$ is undefined in the first place.

The Set-theoretic approach

A limit of the set $S_m := \{c_k\ |\ c_k \text{is in the basket at time } \frac1m\}$ is defined by $$\lim_{m\to\infty} S_m = \bigcap_{m=1}^\infty \bigcup_{n=m}^\infty S_m = \bigcap_{m=1}^\infty [m+1, \infty) = \emptyset$$ This would suggest a value of $0$ coins in the basket at noon.

So the number of coins will be $\infty$ while there will be no coin in the basket at noon. Welcome to infinity.

Answer 3

Our intuition fails us often when we deal with infinite sets, or maybe our definitions regarding infinite sets is misleading.

The problem with the infinite answer is that it assumes that the cardinality commutes with limits. This is not true, at least not with the way we calculate the limits of sets.

Answer 4

This is actually a well known problem called the Ross–Littlewood paradox. The paradox typically, however, does not say anything about the numbering of the coins or which coins are added/removed. In this case it is impossible to say how many coins are left due to what Asaf Karagila said.

In your version, however, it is true that there will be no coins left. There is a very simple proof by contradiction: If there is a coin left in the basket, then the coin has some index k. But we removed coin k on step k. So there must be no coins left in the basket.

Answer 5

Intuitively the answer is ∞ because I added one coin for infinite times.

This intuition attempts to apply a rule of procedure:

After step $k$ there are $k$ coins

therefore

after infinitely many steps there are infinitely many coins.

the correct answer seems to be 0 because every coin numbered k has been removed

This answer responds to the above rule of procedure by saying, "go on then, if you're so clever, what are the numbers on these coins in the basket?"

The intuitive rule of procedure is not tenable. We cannot present an example of a single coin in the basket, let alone infinitely many. Every possible coin can be proved not in the basket after a certain point.

So, we conclude that if we're going to say what happens "after infinitely many steps" of a process, then we need to be very careful what rules of procedure we allow in our reasoning. Otherwise we'll claim the existence of an infinite set that doesn't actually have any elements, and get ourselves in trouble.

This plain-English version of the coins problem more or less cannot be answered, because plain English doesn't provide us with a theory of what happens "after infinitely many steps".

There are interesting mathematical objects such as the Cantor set, where we have to be careful when defining it not to appeal to a flawed intuitive theory of infinite processes.

Answer 6

One possible way of intuiting a solution to this problem is found through "sizes" of infinity. Intuitively, we feel that there are fewer odd natural numbers than there are natural numbers in total, because we can never fill the set of natural numbers purely from the set of odd natural numbers.

In the same way, the number of coins added to the basket is constantly larger than the number of coins removed. No matter how often or how quickly you perform the task (and you head to infinitely fast as 1/k -> 0) you never remove as quickly as you add, meaning the coins added are a "larger" infinity than the coins removed.

The answer to what are the numbers on the coins are in the basket at noon, well "infinity" to "two infinity minus 1". Which is clearly a nonsensical conclusion on the face of it, since no coin has such a label, but we can restate this to answer in a slightly better way:

At each time 1/k, we remove all coins in the basket with numbers less than k, and add new coins numbered 1 to k. We have the same outcome at each step k, except that instead of coins numbered k to 2k-1, they're now numbered 1 to k. At noon, we will have a basket with an infinite number of coins numbered 1 to... well pick up the last coin and you'll know.