Achilles, the Tortoise and the Hotel: Exploring the Infinite
Why infinity is useful, and what kinds of infinity there are
On a beautiful, sunny day, a wise tortoise challenges Achilles to a footrace.
“You want to race me?” Says Achilles. “You’re such a slow animal, and I am the fastest runner in Greece!”
“That’s true,” says the tortoise, “but we can still make it interesting if you give me a head start. Let’s say I start 10 meters ahead of you?”
The distance of the proposed footrace is about 100 meters, and Achilles happily agrees to the head start.
“Great,” the tortoise replies. “Now I will win!”
“Don’t get cocky,” says Achilles. “I will run 100 meters a lot faster than you run 90.”
“You’re the one that’s cocky. And you don’t understand math! You see, to win, you have to first run the 10 meters that I’m ahead of you. Let’s say this takes you 1 second. In that 1 second, I will have crawled 1 meter. You then have to run that 1 meter. But in the time you do so, I will have crawled a bit further! And so on, and so on. So you see, you will never actually catch up to me, let alone win the race!”
“You’re right,” says Achilles. “I give up!”
Anybody reading this will intuitively understand that Achilles would win the race, and that it’s the tortoise who’s wrong at the math. But where exactly is he wrong?
Let’s first model this mathematically. Achilles runs 10 meters in the time the tortoise crawls 1, so he’s 10 times as fast as the tortoise. Assuming they both run at a constant speed, we can draw the following graph:
And we see that Achilles catches up with the tortoise after running a bit more than 1 second. We can even model this with equations, to find an exact answer.
Achilles starts at a distance of 0 meters, and runs 10 meters per second. His distance can thus be modeled as
where
is the distance Achilles covered at time t, and where t is the time in seconds.
With his head start, the tortoise starts at 10 meters. His equation is
When Achilles catches up with the tortoise, they have run equal distances.
gives
which means Achilles catches up with the tortoise after 10/9 seconds. That’s an argument against the point of the story, which is that Achilles will never catch up with the tortoise. But it still doesn’t reveal the flaw in the tortoise’s reasoning!
The key is in this quote by the tortoise: “And so on, and so on.” There is a cycle of Achilles catching up with his current position and the tortoise having crawled a bit further. The tortoise assumes that if they repeat this cycle endlessly (infinitely), Achilles will never catch up to the tortoise, and that’s false.
The tortoise starts out at 10 meters. Achilles takes 1 second to reach that spot, after which the tortoise is at 11 meters. Achilles then takes 0.1 second to reach 11 meters, after which the tortoise is at 11.1 meters. That extra 0.1 meters takes Achilles only 0.01 second, in which the tortoise runs 0.01 meter.
Let’s add those times up. Achilles reaches the first spot in
the second spot in
and the third in
See the pattern? At every spot, a 1 is added after the decimal point.
grows with each step, but it’s growth is bounded: it will never reach 2 seconds, for example. What value will it reach? 1.111…, or 1.1 repeating. And that’s just 10/9, the value we got earlier!
Not convinced that 1.111.. = 10/9? Consider this:
The tortoise is correct in that we can model the footrace as a series of cycles of Achilles catching up with his current position and the tortoise having crawled a bit further. But his conclusion — that Achilles will never catch up with him — is incorrect, because an infinite number of those cycles still only take a finite amount of time: 10/9 seconds.
This teaches us something important: that infinity, while seemingly mysterious, does make sense as a concept. Let’s explore it a bit more.
On the beautiful planet of Paradoxica, overlooking Infinity Ocean, lies Hilbert’s Hotel. With a dock on one side and a bus station at the other, its location attracts many guests. Many, many guests…
You see, Hilbert’s Hotel is no ordinary hotel: it has an infinite number of rooms. It is currently fully booked though: there’s an infinite number of guests staying at Hilbert’s Hotel, so every room (labeled 1, 2, 3, etc.) you can think of is occupied.
Imagine you’re the manager of the hotel. A guest shows up, and asks you whether he can stay for the night. You might think that there’s no room available, but fortunately, you can make room!
How? By asking every person staying at the hotel to move up 1 room. So the guest of Room 1 goes to Room 2, the guest of Room 2 goes to Room 3, etc.
This process makes Room 1 free for the new guest! And note that, although the hotel was full, everybody is assigned a room. Nobody has to go home. Call the guest in Room 1 Guest 1, the guest in Room 2 Guest 2, and generally, the guest in Room n Guest n. Then any guest you can think of is assigned a room: Guest n goes to Room n + 1, for n = 1, 2, 3, …, and there is no x for which Guest x has no room.
Soon, more guests show up: a bus stops, and 100 passengers step out, all looking for a place to sleep. No problem: you send every guest 100 rooms down the line. Guest n to Room n + 100 for n = 1, 2, 3, … Now Rooms 1–100 are free!
But then, a special bus shows up: a bus with an infinite number of seats. Of course, all these seats, numbered 1, 2, 3, …, are filled. All passengers of this infinite bus want to stay at your hotel. What should you do?
You can do a nice trick here: send Guest n to Room 2n. So Guest 1 goes to Room 2, Guest 2 goes to Room 4, etc. Now every guest is in an even room, leaving all odd rooms empty!
Now, the infinite bus passenger with Seat 1 can go to Room 1, the passenger with Seat 2 can go to Room 3, etc. In general, the passenger with Seat n goes to Room 2n - 1.
So, amazingly, even though your hotel was already full, you could still fit an extra infinite number of guests!
But the day isn’t over yet. Suddenly, an infinite number of buses, with license plates 1, 2, 3, …, arrive. Each bus is like the bus before: infinite seats, infinite passengers. What do you do now?
Well, you can start by sending Guest n to Room 2n, as before. This way, you at least have an infinite number of rooms available! What’s next?
Let’s start with the bus with license plate 1: call it Bus 1. Assign the passenger on Seat 1 to Room 3¹ = 3, the passenger on Seat 2 to Room 3² = 3 * 3 = 9, the passenger on Seat 3 to Room 3³ = 3 * 3 * 3 = 27, etc. Note that all powers of 3 are odd: multiplying an odd number by an odd number gives an odd number. And the odd rooms are all available! Everyone on Bus 1 gets a seat.
What about Bus 2? We use the same process as for Bus 1, but now with 5 instead of 3: 5¹ = 5, 5² = 25, 5³ = 125, etc. These powers are all odd as well!
But wait a second. How do we know the powers of 5 and 3 don’t overlap? Aren’t we assigning people to rooms already occupied by Bus 1 passengers?
No, we’re not. 3 and 5 are both prime numbers: they can only be divided by 1 and themselves. And there’s a beautiful theorem — the Fundamental Theorem of Arithmetic — that says that every natural number (1, 2, 3, 4, …) can be represented as a product of prime numbers.
For example, 12 = 2 x 2 x 3, 14 = 2 x 7, etc. What’s more, these prime number products are unique: if we want to write 12 as a product of prime numbers, we have to use exactly two 2s and one 3.
3¹, 3², 5¹, etc., are all products of prime numbers; therefore our method can never assign the same room number twice! If that were the case, then that room number was represented by two different products of prime numbers, which the Fundamental Theorem of Arithmetic says is impossible.
For Bus 3, we can use the next prime number: 7. For Bus 4 we use 11, then 13, etc. There are infinitely many prime numbers, so we have a prime number for every bus!
So once again, everyone is assigned a seat.
You have given a hotel room to every guest of an infinite number of infinite buses! You’re getting tired of a job well done, but the day still isn’t over. You look at the ocean, and see an infinite number of ferries arrive…
Each ferry — numbered 1, 2, 3, … — carries an infinite number of infinite buses. All buses carry an infinite number of passengers, and they all want to stay at your hotel.
No problem! You got this. First, assume the ferries are named Ferry 1, Ferry 2, etc. On Ferry 1, we have Bus 1, Bus 2, etc., and each bus has Seat 1, Seat 2, etc. Ferry 2 also has Bus 1, Bus 2, etc., and so on.
Once again, we move every guest in the hotel room: Guest n goes to Room 2n, causing all odd rooms to be free.
Now we have to assign hotel rooms to all the passengers on the ferries. We can do this by extending the method of the infinite number of infinite buses.
For example, the passenger on Seat 2 in Bus 2 on Ferry 3 would get a hotel room as follows. For Ferry 3, we take the third prime number: 5. For Bus 2, we take the second prime number: 3. We raise 3 to the power of the seat number: 3² = 9. Then, we raise the ferry’s prime number (5) to the power of 9: 5⁹ = 1953125. Our passenger gets assigned to Room 1953125!
Note that the first step — raising a prime number to the power of the seat number — gets you a unique number, just as before. Raising a prime number to that unique number must once again give a unique number, according to the Fundamental Theorem of Arithmetic. Each guest gets a unique (and odd!) hotel room.
Note that, with this method, room numbers get large really quickly — just try to calculate the room number for the passenger on Seat 99 in Bus 99 on Ferry 99. But large doesn’t really mean anything in a hotel with infinite rooms!
More importantly, note that this method is easily extendable to deeper “levels”: if we had some kind of super-ferries carrying infinite numbers of ferries (each with infinite numbers of infinite buses), we could assign the passenger on Seat 2 in Bus 2 on Ferry 3 on Super-Ferry 2 Room
WolframAlpha tells me this Room number has 931878 digits. But, you know, infinite rooms.
You’re not done, but you knew that by now. You see another bus waiting at the bus station. Of course, it’s infinitely long. But this one is different from all the previous buses: it has no seats. The passengers are all standing in the bus.
The driver says: “The passengers in my bus are numbered, but not in the usual way. They each have an infinitely long number assigned to them. We have passenger 111111111…, passenger 121212121…, passenger 987987987…, etc. For each number you can create this way, there’s a passenger. I heard your hotel has infinite rooms though, so can all my passengers stay here?”
You have done an amazing job so far giving rooms to an infinite number of infinite numbers of infinite groups of people, but you have to tell the bus driver no. You can’t do this.
Why? Because no matter what method you come up with to assign hotel rooms to the passengers of this bus, there will always be a passenger that isn’t assigned a room.
Let’s say you come up with a way of assigning hotel rooms to the passengers. So, for example, Passenger 111111111… gets Room 1, Passenger 211111111… gets Room 2, 311111111… gets Room 3, and so on. Imagine putting these passengers on a list, with their room next to them:
The driver can now definitely point to a Passenger that doesn’t have a room assigned to them. How? By taking the first digit of the first passenger on the list (Passenger 111111111…) and adding 1, taking the second digit of the Passenger 2 and adding 1, etc. If the digit happens to be 9, it becomes 0.
Combine all the digits acquired this way into a single number. That passenger did not appear on your list! After all, the number is different from Passenger 1 in at least the first digit, it’s different from Passenger 2 in at least the second digit, etc. In general, it’s different from Passenger n in at least the nth digit.
So no matter what you come up with, the driver can point to a passenger you haven’t assigned a room.
In the previous examples, passengers were numbered in the normal way: 1, 2, 3, …, and the method of assigning rooms made sure we couldn’t point to a passenger who didn’t have a room. Even though each infinite bus had infinite passengers, this infinity was countable: you could number all passengers using the natural numbers (1, 2, 3, …).
In contrast, the final, no-seat bus had an uncountably infinite number of guests: even if you tried to assign all of them a natural number, you could always point to one that didn’t have one assigned to them. Another example of an uncountably infinite set is the amount of real numbers you can put between 1 and 2 (so 1.1, 1.05, 1.000245, etc.).
There are at least two things that are interesting about Hilbert’s Hotel:
- Even if every room is occupied, you can still fit more guests, even (countably) infinite groups!
- There’s still a limit: you can’t fit uncountably many guests.
The fun thing here is that, if you’re new to infinity (and maybe even if you’re not), (1) might seem paradoxical; but once you’re used to it, (2) seems paradoxical.
Next to Hilbert’s Hotel, on Paradoxica, lies Hilbert’s Bank. Obviously, this bank has a countably infinite amount of money. Curious, you walk into the bank, and the manager proposes a game.
“I’ll toss a fair coin,” she says. “If it’s tails, you win $2. If it’s heads, I’ll toss the coin again. Is it tails? Then you win $4. If it’s heads, I’ll toss again, and so on.”
“So your stake starts at $2 and doubles when heads appears, and the game stops if (and when) tails appears.”
“How much money are you willing to pay to play this game?”
You respond: “$10, no more. It seems like fun to play the game, but I won’t make much money.”
“Ah, but that’s where you’re wrong,” say the manager. “Your expected payoff is infinite! Since the coin is fair, there’s a ½ probability it comes up tails on the first run. So you have a ½ probability of making $2. If the coin comes up heads on the first run, there’s a ½ probability it comes up tails on the second run, in which case you’ll make $4. This outcome has a probability of ½ x ½ = ¼. You’ll make $8 with a probability of ⅛, etc.”
“Therefore, your expected payoff is $2 x ½ + $4 x ¼ + $8 x ⅛ + … = $1 + $1 + $1 + … = $∞. You should therefore be willing to pay all the money you have to play this game.”
My educated guess is that you intuitively disagree with the bank manager, and that you feel it would be ridiculous to pay all your money to play this game. But where exactly is the error in the manager’s reasoning? Shouldn’t you be willing to pay anything for an expected infinite payoff?
A standard response is to say monetary payoffs have diminishing marginal utility: that is, each extra dollar you win has less value than the previous one. This makes sense: winning, say, $100 is awesome, but if you already won $10,000, an extra $100 isn’t that awesome anymore.
Utility measures how much something is actually worth to you, and it is measured in utils. Winning $100 might be worth 100 utils to you. If we except the principle of diminishing marginal utility here, than winning $10,000 isn’t worth 100 times as much as winning $100 (which would be 10,000 utils).
So how should we value money? Well, we could use the natural logarithm (ln):
Now the expected monetary payoff is still infinite, but the expected utility isn’t: 0.69 x ½ + 1.39 x ¼ + 2.08 x ⅛ + … isn’t infinite. That appears to resolve the paradox of not wanting to pay anything for an expected infinite payoff.
But the heart of the paradox remains. What if the stake doesn’t double on each round, but instead equals $e², $e⁴, $e⁸, … (where e is Euler’s Number)? Then our V() gives the following utilities:
Now the utilities are the same as the original monetary payoffs, which means our expected utility is infinite. The paradox is back!
Multiple other solutions to the above paradox — known as the St. Petersburg Paradox — have been proposed. My own intuition is that this paradox points at an actual problem with the way we calculate expected utilities. One reason is that, although your expected utility is infinite (in the final discussed version), you will definitely earn only a finite amount of utils. No matter how many rounds the game lasts, you’ll earn a finite amount of money, and thus get a finite amount of utils.
It’s not weird that the expected utility won’t ever manifest itself as an actual outcome. For example, if I have 50% chance of winning 1 util and 50% chance of winning 3 utils, I will win an expected 2 utils, even though I will never actually make 2 utils: I will make either 1 or 3. But to always earn less utils than the expected infinite amount suggests (to me) there’s something wrong with the calculation of that expected amount.
What do you think?
Next in Paradoxology: Monty Hall, Monty Fall and Monty Crawl: A Deep Dive Into Probabilities
