Can an Infinite Hotel Run Out of Rooms?

David Leshem

What if I told you that I would pay for your trip to a dream destination? You have the location picked out, the activities planned, and the flights booked. Lastly, you need a place to stay. You choose the fanciest hotel in town. Unfortunately, this hotel has a finite number of rooms, and due to some procrastination, they are fully booked. What a shame. Luckily, you hear about an “infinite hotel” that is just a few doors down from where you wanted to stay. The name of this hotel is Hilbert’s Hotel, named after the findings of famous mathematician David Hilbert.

Hilbert’s Hotel

Hilbert’s Hotel has an infinite capacity, and the management promises that it can find space for anyone. Let’s investigate if this is true. Each room is assigned a Natural number starting from 1, 2, 3, and extending to infinity. Imagine the hotel is full. There are an infinite number of people staying in the hotel with an infinite number of rooms. However, they can accommodate you. The manager of the hotel will simply ask the person in room 1 to move to room 2, the person in room 2 to move to room 3, and so on. Essentially, each guest will move from room $n$ to room $n+1$ . Since this is a hotel with infinite capacity it will be able to accommodate these moves and you will then be placed in room 1. While there isn’t a last room, it is important to remember that there is always a “next” room available.

Adding a Finite Number of Guests

Instead of just one person showing up, imagine if there were a party of 100. The hotel would still be able to accommodate. Each guest would have to move from room $n$ to room $n+100$ to create the necessary space.

Here, I want to remind you that the set of all the rooms is the set of all $\mathbb{N}$ . In class, we discussed how $\mathbb N$ is an example of a countably infinite set. These past two examples include expanding the countably infinite set by finite numbers, thus maintaining the level of infinity.

An “Infinity Bus”

What if an “infinity bus” filled with an infinite number of tourists arrived at the Hilbert Hotel? They would still be able to accommodate. To achieve this, the person in room 1 will be moved to room 2, the person in room 2 will be moved to room 4, and so on. Here, hotel guests are moving from room $n$ to room $2n$ . As we learned in class, every even number can be represented by $2n$ for some integer $n$ , therefore every even-numbered room will be occupied. This also means that every odd-numbered room at the hotel will be available. The odd numbers, a subset of $\mathbb N$ , is also a countably infinite set. Therefore, the manager has successfully opened up enough rooms to accommodate everyone on the infinity bus.

Infinite Infinity Buses

What if an infinite number of infinity buses arrived? They would still be able to accommodate. There are a few different ways that the hotel manager could choose to go about this. One way in which we can solve this connects to the subject of prime numbers for the Number Theory final project. Theorem 7.2.22 posits that there are infinitely many primes. Knowing this, we can create infinitely many spots for each person on each infinity bus. First, the hotel management will move the current guests. Taking the first prime number, 2, these guests will move from room $n$ to room $2^n$ . Next, we need to consider the first infinity bus. Imagine the individuals on this bus each sat in a seat with a uniquely assigned natural number $k \in \mathbb N$ . For this bus, we will use the second prime number, 3, and place individuals in rooms $3^k$ . The passengers on the next bus will be placed in rooms $5^k$ Since there are an infinite number of primes, each bus will be designated a unique prime base that will be raised to the kth power based on which unique seat someone is sitting in. While there will be plenty of vacant rooms, the infinite hotel will still profit by accommodating an infinite number of infinity buses.

Take a moment and try to think why there will be vacant rooms. Can you list 3 of them?

Uncountable Infinity Bus

Now consider a bus with an infinite number of people. However, on this bus, there are no seats. Instead, each individual is identified by an infinite sequence of the numbers 0 or 1. Recalling Cantor’s diagonal argument from lecture 20, we learned that although there are an infinite number of individual sequences that are each infinitely long, it is always possible to create a new sequence. Here, the management team fails to assign each individual to a unique room. Take the first number of the first person and flip it, then the second number of the second person and flip that. If you continuously repeat this process, you are guaranteed to come up with a new combination of 0s and 1s of someone who has not yet been placed in a room.

The number of rooms in the Hilbert Hotel is countably infinite, which means there are as many rooms as there are positive integers 1 to infinity. However, the number of people on the bus is uncountable because there are always more individuals to add. There is no surjective function that can map every natural number to every person on the bus. Thus, the cardinality of the set containing each hotel room is not equal to the cardinality of the set containing each person on the bus of 0s and 1s. Here, we finally see an example of Hilbert’s Infinite Hotel running out of space.

Conclusion

Thank you for taking the time to read this post and learn more about the complexities of infinity and cardinality. I hope this article has piqued your interest in exploring more mathematics topics related to our course. Below, I am including links to two Youtube videos that will also show a nice illustration of Hilbert’s Hotel.

Sources

Veritasium. “How An Infinite Hotel Ran Out Of Room.” YouTube, uploaded May 10, 2021, https://www.youtube.com/watch?v=OxGsU8oIWjY.
Jeff Dekofsky. “The Infinite Hotel Paradox.” YouTube, uploaded by TED-Ed, Jan 16, 2014, https://www.youtube.com/watch?v=Uj3_KqkI9Zo.

Answer to the challenge question: The rooms that are not powers of prime numbers will go unfilled in the “Infinite Infinity Buses” section. This, however, does not mean that the hotel cannot accommodate the infinite number of infinity buses. The manager is still able to map each individual to a room because there exists an infinite number of prime numbers. Some unfilled rooms are 6, 10, 12, etc.

2 Comments


June 2, 2023
jrh7328

Your analysis of the Hilbert’s Hotel problem was very thoughtful and insightful. The video that you provided had a great visual for the different concepts that you touched on, and this was a strong explanation of the concepts that we discussed in class like countability, Cantor’s diagonal proof, and cardinality. You helped me understand these concepts to a much greater extent and I enjoyed reading your article. One question is more of a question about infinity itself. How exactly can a hotel be full if it is infinite? I understand that the set is countable, but if it is infinite how can we actually count it? This is something I struggled with during class as well, but it’s a thought related to this visualization of the concept. Overall, you did a very strong job portraying this information and I thoroughly enjoyed reading your post.

June 3, 2023
uno

Very interesting post David! I’ve seen the idea of Hilbert’s Hotel on different Youtube videos and while randomly browsing the web, but seeing it after actually understanding how cardinality works puts a interesting new perspective on it! I found it really cool how you related the idea of the infinite buses and Cantor’s diagonal theorem in order to explain how the infinite hotel cannot fit infinite buses of incoming guests. One question I have regarding the post though, is if the hotel were also uncountably infinite, would the infinite amount of buses be able to fit in? Of course, while the idea of cardinality from class is able to answer the question, I wanted to know if there would be any changes when it gets applied to the hotel 🙂