Hilbert's Hotel: Why a Fully Booked Infinite Hotel Never Turns You Away

By Martin McBride, 2026-07-23

Tags: bijection cardinality countable infinity cantor set theory veridical paradox prime factorisation hilbert thought experiment
Categories: paradoxes sets infinity
Level:

AP / A Level

Bachelor's / Undergraduate

Recreational Maths

Picture a hotel with infinitely many rooms. Room 1, room 2, room 3, and so on, forever. Tonight, every single room is occupied. A "No Vacancy" sign glows above the entrance. And yet, when a weary traveller shows up at midnight, the manager smiles and says: "Of course, right this way."

Welcome to Hilbert's Hotel. It is a thought experiment dreamed up by the mathematician David Hilbert to make one simple point: infinity does not behave the way you think it does. Once you see how this hotel manages always to have room, you'll understand something profound about the nature of infinite sets.

Let's check in.

The latecomer

So, it's midnight. Every room is full. This diagram shows the rooms (numbered r1, r2...) and the guests in the rooms (numbered g1, g2...):

Hilbert's hotel

Guest 1 is in room 1, guest 2 is in room 2, and so on. There are infinitely many guests occupying infinitely many rooms, with one guest in each room.

A single new guest arrives at reception, tired and expecting to be turned away. The manager isn't worried.

Here's what the manager does. He asks the guest in room 1 to move to room 2. The guest in room 2 moves to room 3. The guest in room 3 moves to room 4. And so on. Every guest moves from their current room, $n$, to the next room $n+1$.

Every guest moves to the next room

If we tried to do this in a normal hotel with, say, 100 rooms, it would not work. The guests in rooms 1 to 99 could move to rooms 2 to 100, no problem. But the guest in room 100 would need to move to room 101, and there is no such room.

But in an infinite hotel, there's no "last room" to worry about. The rooms go on forever. The guest in room n can always move to room n + 1, no matter how big n might be.

So every existing guest still has a room, just one number higher than before. And now room 1 is empty, ready for the newcomer:

Every guest moves to the next room

The new arrival, a1, moves into room 1, and everybody is happy.

It can be difficult to get your head around this concept. Infinite or not, if the hotel is full it is full, surely? Well, you are perhaps thinking of infinity as being an ordinary number. But it is not.

Here's the difference. In a hotel with 100 rooms, there is a room numbered 100. But in an infinite hotel, there is no room numbered infinity. Every room in the hotel has an ordinary, finite number. It is just that those numbers go on forever. So every single one of the guests is in a room with some unique number n, therefore each guest can move into room number n + 1, no matter how big n might be. They can all change rooms, leaving room 1 free.

If you still don't believe it, then which guest will be left without a room? Guest 100 can move to room 101, guest 1,000 can move to room 1,001, guest 1,000,000 can move to room 1,000,001. Every guest is able to move into the next room, no matter what their current room number is.

It is also worth remembering that this is a thought experiment. An infinite hotel cannot exist in reality. Even if the entire surface of the Earth were covered in hotel rooms, there would still be a finite number of rooms. Vast, but finite. So the logic above would not apply. This huge but finite hotel could become full. But a truly infinite hotel cannot.

Bijections

One way to think about this is that we have mapped the set of original rooms onto a different set of rooms. Each room n is mapped onto a different room n' using the formula:

n' = n + 1

The set of numbers 1 to infinity is mapped onto the set of numbers 2 to infinity. This is a one-to-one mapping (each n maps onto a unique n'), so it is reversible. If we know n' we can find n:

n = n' - 1

This type of reversible mapping is called a bijection. Since there is a one-to-one correspondence between the elements n and n', the two sets must be the same size. That is true even though set n contains all the numbers in n' plus an extra number 1, that isn't in n'.

When dealing with infinite sets, we use the term cardinality rather than size, because size implies that we can somehow count all the elements. The set of all natural numbers has a cardinality called countably infinite. Any set that can be mapped onto the natural numbers by a bijection is also countably infinite. This means that the number of rooms in Hilbert's hotel is also countably infinite.

There are other cardinailities that are larger the countably infinite, see Countable and uncountable sets.

The infinite coach

Now let's look at a slightly different situation. Instead of a single new arrival, a whole coach load of people turns up at the hotel. But this is a very special coach carrying infinitely many new guests, numbered a1, a2, a3, and so on forever. Surely this is a problem? The hotel is still full, and now there isn't just one extra guest to fit in. There are infinitely many guests.

The manager knows exactly what to do. This time, every existing guest is asked to move from room $n$ into room $2n$. So the guest in room 1 moves to room 2. The guest in room 2 moves to room 4. The guest in room 3 moves to room 6. In general, whoever was in room $n$ now lives in room $2n$:

Every guest moves from n to 2n

Notice what this does: every existing guest now occupies an even-numbered room. That means every odd-numbered room (room 1, room 3, room 5, and so on, infinitely many of them) is now empty.

So the manager puts passenger a1 into room 1, passenger a2 into room 3, passenger a3 into room 5, etc. In general, passenger $k$ goes into room $2k - 1$. Every single passenger from the coach gets a room. Every original guest still has a room. Nobody shares, nobody sleeps in the car park. Here is what the hotel looks like when the new guests move in:

Each new guest k goes in room 2k - 1

Once again, this is just a bijection, but this time it is a slightly more elaborate pairing that divides the hotel into two infinite chunks (the evens and the odds) and gives one chunk to the old guests and one chunk to the new. The set of whole numbers, it turns out, contains room for two full copies of itself. This tells us something wild - an infinite set can be the same "size" as a set that seems, at first glance, to be twice as big.

Infinitely many infinite coaches

What could be worse than a coach with an infinite number of passengers? Well, suppose the manager looks out of his window and sees not one coach, but infinitely many coaches, each queued up one behind the other. We will call these c1, c2, c3, and so on forever. And, as before, each coach carries infinitely many passengers.

This feels like it should finally break the hotel. We don't just have one extra infinity-large set of guests. We have an infinite number of infinite sets of guests. Surely there's no way to fit an infinity of infinities into a mere infinity of rooms?

As a first step in solving this problem, we need to find a new way to number the incoming guests. We have infinitely many coaches each containing infinitely many guests, so let's identify each new guest by their coach and their seat number on the coach.

The guest who arrives on seat 1 of coach 1 can be called (s1, c1).
The guest on seat 2 of coach 1 is (s2, c1), and so on.
The first 2 guests on coach two are called (s1, c2) and (s2, c2), and so on.
The guests on coaches 3, 4, 5... are named in a similar way

This gives a unique identity to every passenger on every coach. We can represent this as a table:

All guests on all coaches

The top row of this table represents the guests who are already staying at the hotel: g1, g2, etc. The first 5 are shown, but of course the row is infinitely long.

The second row represents the guests on coach 1, the third row represents the guests on coach 2, and so on. The table is infinite in both directions. There are infinitely many columns because each coach has infinitely many seats, and there are infinitely many rows because there are infinitely many coaches.

If we want to fit all these guests into the hotel, we need to find a way to give each guest a unique hotel room number. But that looks impossible. For example, we start on the first row, we can put customer g1 in room 1, g2 in room 2, etc. But the first row is infinitely long, so we will never reach the end. So we will never get around to finding rooms for row 2 (ie the customers in coach 1).

But it isn't impossible, we just need a bit of lateral thinking. Or, in this case, diagonal thinking. We can visit all the squares in the grid in this order:

Ordering guests on all coaches

First we assign guest g1 to room 1.

Then we move along and assign g2 to room 2. But here is the sneaky part. We move down diagonally and assign (s1, c1) to room 3.

Then we go back to the top row and work down diagonally again. g3 gets room 4, (s2, c1) gets room 5, (s1, c2) gets room 6.

Then we do the same again. g4, (s3, c1), (s2, c2) and (s1, c3) gets rooms 7, 8, 9 and 10.

We can carry on doing that forever. Every diagonal is finite in length (the first has 1 cell, the second has 2, the third has 3, and so on), so we will eventually find a room for every guest.

There is an infinity of infinities of guests, but the hotel still absorbs every single one of them into its ordinary, single infinity of rooms.

Another way to do it

If we look at this problem a slightly different way, we can find an alternative approach. We just put a lot of effort into an elaborate scheme to put exactly one guest in every room, but there is another way to look at this. We have infinitely many rooms, so:

We don't need to ensure that every room has a guest.
All we need to do is to make sure that we don't put two guests in the same room.

If we can find a way to assign a unique room number to every guest, then that is enough. It doesn't matter if that leaves some rooms empty.

One way to do that is to use prime factorisation. We know that any integer can be expressed as a unique product of prime numbers. For example:

$450 = 2 \times 3^2 \times 5^2$

For any positive integer n, there is only one way to express n as a product of primes. That means that every product of primes corresponds to a different positive integer.

How does this help us? Well, we could create a mapping between a particular seat on a particular coach and a room number. For example, we could use the following formula to calculate a room number for the passenger in seat number p on coach number q:

$(sp, cq) \implies = 2^p \times 3^q$

Since this is a prime factorisation, the room number for any particular p and q is unique. So every passenger will get a different room.

For example, the passenger in seat 2 on coach 1 will be sent to room 12. No other passenger will be sent to room 12:

$(s2, c1) \implies = 2^2 \times 3^1 = 12$

The passenger in seat 4 on coach 2 will be sent to room 144. No other passenger will be sent to room 144:

$(s4, c2) \implies = 2^4 \times 3^2 = 16 \times 27 = 144$

This means that the hotel manager can look at each guest's coach ticket and tell them which room to go to. The guest who arrived on seat 2 of coach 1 is sent to room 12. The guest who arrived on seat 4 of coach 2 is sent to room 144.

This scheme ensures that every guest gets their own room. But notice that some rooms in the hotel will be left empty. In fact, a room will not be occupied if it has any prime factors other than 2 or 3. Room 10 won't be occupied, for example, because 10 is divisible by 5.

In fact, the vast majority of rooms will not be occupied, because most numbers have prime factors other than 2 or 3. Almost all the rooms in the hotel will be empty. Previously we had infinitely many guests in the hotel, and every room was full. Now we have infinitely more guests but almost every room is empty!

Just one minor point. In the original example, we took account of the existing guests as well as the guests arriving on coaches. With this new method, we are only taking account of the guests arriving on coaches. That is to simplify the description. If we wanted to include the existing guests too, we could pretend they arrived on coach 0. The existing guests would be moved to rooms 2, 4, 8, 16...

Adding an extra level

We will add one extra level. Suppose the coaches arrive on a ferry. Each ferry carries an infinite number of coaches. What happens if an infinite number of ferries all arrive at the hotel at the same time?

So now we have an infinite number of ferries, each holding an infinite number of coaches, each holding an infinite number of passengers. An infinity of infinities of infinities. Can the hotel accommodate all those guests? Of course it can.

Each guest is now uniquely identified by which seat they had, on which coach, and on which ferry. We can calculate the room number for the passenger in seat number p, on coach number q, on ferry number r, like this:

$(sp, cq, fr) \implies = 2^p \times 3^q \times 5^r$

We have added an extra prime factor of 5. Once again, each guest (ie each unique combination of p, q and r) will be given a unique room number.

So is this really a paradox?

This is a paradox, but it is a specific type of paradox. It doesn't involve a contradiction or an inconsistency. It is a veridical paradox. That is a type of paradox that seems absurd or contradictory but actually turns out to be true once you understand the mathematics.

It is also sometimes called a paradox of infinity or a set-theoretic paradox. These are particular types of veridical paradoxes that occur when looking at infinite sets.

What's really happening is that our everyday intuition about size, based entirely on our experience with finite collections of things, simply doesn't transfer to the infinite. "Full" stops meaning what you think it means. "Bigger" and "smaller" need new definitions, which is exactly what bijections give us. A bijection is a rigorous way to say two infinite sets are "the same size" without ever needing to count them.

Hilbert introduced this hotel in a 1924 lecture to make that point vivid and unforgettable. Hilbert himself never published his lecture, but fortunately his colleague Richard Courant did.

The lecture wasn't there to trick anyone, but to train the imagination for ideas Georg Cantor (the mathematician who first studied the sizes of infinite sets) had proven decades earlier. Ideas such as Galileo's paradox and the Cantor set.