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
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.
No comments:
Post a Comment