Infinite Hotel Paradox, Continued
This is part 2 of the Infinite Hotel Paradox, check out part 1 as well →
We’ve already talked about how the manager of a hotel with an infinite number of rooms in which every room is filled makes space for more guests, even an infinite number of guests! But what happens when an infinite number of infinite guests arrive at the hotel?
Can we organize the guests so that there is enough rooms for everyone?
Part 3: An Infinite Number of Infinite Busses
One night the manager of the Infinite Hotel, which has no vacancy, looks out the window to see an infinite number of busses each filled with an infinite number of room-seeking guests?
Can she make room for an infinite number of infinite people in the infinite hotel although the hotel is completely full?
In Search of an Elegant Solution
As we discussed in the last post, the key to solving these paradoxes is to find a mapping (i.e. bijection) from our current guests, which are naturally numbered, to a new set that leaves enough room for the new guests.
Recall that when we needed to make room for 5 guests, we move everyone in the hotel up 5 rooms, leaving the first 5 empty. And when we needed to make room for a countably infinite set of guests, we moved all of our current guests to the even numbered rooms, leaving an infinite number of odd numbered rooms for our new guests.
So what clever device can we employ to move our current guests that will free up an infinite number of infinite rooms?
A Helpful Fact
At the end of the last lesson, I also gave you a little hint:
The set of all prime numbers is countably infinite.
Although this may seem like an obscure fact, it’s a result that’s been known for centuries. Our man Euclid showed us this was true back in 300BC. In fact, we proved this result a while back in this post.
Since the set of primes is countably infinite, we can take the guests and systematically assign them to powers of prime numbers (which we know will be unique by the prime factorization theorem).
How to Move the Current Guests
For starters, we’ll move the infinite set of guests currently in the hotel from their current room numbers (i.e. the natural numbers) to powers of the first prime number, 2.
So the guest in room 1 goes to room 2¹= 2, the guest in room 2 goes to room 2² = 4, and so on.
Bus #1’s Room Assignments
Then we’ll take the guests from the first bus and assign them to powers of the next prime number, which is 3, using their seat numbers as the powers.
For example in this first bus we’ll move the guest from seat 1 to 3¹ = 3, the guest from seat 2 to 3² = 9, and so on.
Bus #2’s Room Assignments
We’ll continue this pattern using the next prime number as the base for the next bus.
And So On…
Because we have an infinite set of prime numbers, theoretically we can continue using the next prime as the base for each of the countably infinite busses. And since raising the prime number to a new power produces a brand new room number, we can locate rooms for the infinite guests on each bus.
We did it! We’ve found a way to ensure a unique room for an infinite number of infinite guests!! And crazy as it may seem, we’ll leave a lot of rooms unoccupied in the process.
