# A strange puzzle having two possible solutions

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.

-
Strongly related. I think there is also an answered duplicate, but I haven't found it yet. – Daniel Fischer Jul 17 '14 at 13:47
Looks like a classical "limit doesn't exist" situation – Ewan Delanoy Jul 17 '14 at 13:50
Assume infinity, derive paradox, blame Cantor! – Winther Jul 17 '14 at 13:52
A splendid illustration that limits and functions don't always commute (lim_k→∞(|X_k|) != |lim_k→∞(X_k)|, where k ∈ ℕ, X_k = [k+1, 2k+1] ⊂ ℕ). – outis Jul 17 '14 at 22:09
There is a similar puzzle called "Thompson's lamp". – Kartik Jul 18 '14 at 9:37

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.

-
"Since no even indexed coin was ever removed, the basket contains an infinite amount of coins." I don't follow you here. The question says that at 1/k before noon, coin k is removed. E.g., coin 6 (with an even index) would be removed at 1/6 before noon. – Joshua Taylor Jul 17 '14 at 16:55
No, that is just the intuitive answer given by the OP as to why this process would yield an empty basket. It is not necessary that this happens. – Asaf Karagila Jul 17 '14 at 16:58
Oh, I see, you're not assuming that the index is the number mentioned in the question; you're assigning new indices to the coins. This has the interesting result that whereas the question says which order the coins are removed in, Case III doesn't. The question is actually written such that both of the coins put in when the first is removed will be removed on the next two iterations. – Joshua Taylor Jul 17 '14 at 16:58
I don't understand your comment. It says, right in the question: "A friend of mine asked me the following question: '… At noon less 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 1/k he takes the coin number k and put two other coins.'" Given that description, you can say precisely at which time each particular coin would be removed. Coin k is removed at time 1/k before noon. – Joshua Taylor Jul 17 '14 at 17:00
I'll be very happy to hear the objections of whoever downvoted. I'm usually trying to improve my answers. – Asaf Karagila Jul 17 '14 at 22:20

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.

-
Contra-contra: If there is not a coin with some index $k$ left in the basket, we must have removed it, and added coins with indices $k+1, k+2$. But we assumed no coins in the basket, so there must be coins in the basket. – Ollie Ford Jul 17 '14 at 22:59
It seems the argument that no coin is in the basket is solid. Which means that given a sequence of sets, the cardinality of the limit is not the limit of the cardinality. Note also one could change the process to always have exactly 10 coins in the basket after every step, yet each coin eventually removed from the basket too, leaving none. – Neil W Jul 18 '14 at 6:56
@OllieFord Where is a contradiction? Yes we added coins k+1 and k+2, they just got removed later. – Cthulhu Jul 18 '14 at 8:16
@OllieFord We assumed there was at least one coin and chose k to be that coin that was in the basket. So the fact that it is not there is a contradiction. – Dylan Stephano-Shachter Jul 18 '14 at 13:20
@OllieFord It is important to keep in mind that induction allows us to prove a statement for any natural number n. It does not, however, allow us to prove the statement for "infinity" (or $\omega$). – Dylan Stephano-Shachter Jul 21 '14 at 15:49

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.

-

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.

-
That can't be right. This is like saying that the limit of the sequence of sets $A_n=[n,\infty)$ cannot be $\varnothing$ because at each step, $|A_n|>0$. – Asaf Karagila Jul 17 '14 at 13:54
@AsafKaragila okay, but taking the partial sums and showing that each is $\ge 1 > 0$ does indeed show that, since that would be analogous to taking the partial intersections and showing that $$\liminf_{M\to\infty} \bigcap_{n\le M} A_n = \infty$$ – AlexR Jul 17 '14 at 13:56
But this is not a question about the convergence of real-valued series. This is a question about "how many", so it is a cardinal question to begin with. So real analysis is just the wrong tool to deal with it. (I didn't vote, by the way.) – Asaf Karagila Jul 17 '14 at 14:01
I think this is a correct answer to this question: "What is the limit of the number of coins at time $t$ as $t$ approaches noon from below." But the OP asked how many coins are there at noon. The answers to these questions are the same only if the function is continuous. Is it? – David K Jul 17 '14 at 14:02
Alex, your answer assumes that $card(\lim A_n)=\lim(card (A_n))$, why is this true? Your intuition tells you this is true, but in math intuition doesn't replace proof. – N. S. Jul 17 '14 at 14:06

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.

-
What on earth does the phrase "the cardinality commutes with limits" mean in this context?!? You should try to make your answer more in-line with the question...try and explain it a bit more... – user1729 Jul 29 '14 at 14:52
@user1729 It simply means that our intuition tells us that for a sequence $A_n$ of sets we have $$\lim_n (\mbox{card} A_n)=\mbox{card} (\lim_n A_n) \,.$$ And that is not true. In mathematics, commutes simply means you can interchange their order... – N. S. Jul 29 '14 at 15:59

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.

-

## protected by arjafi♦Jul 18 '14 at 7:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).