Hilbert's hotel

Suppose you're a hotel manager and your hotel is full. That's great, of course, but there's always the temptation to squeeze in more guests. In real life, this might mean clearing out the broom cupboards and getting bad reviews on Trip Advisor, but in the world of maths it's no problem. As long as your hotel has infinitely many rooms, that is.

Welcome to Hilbert's hotel!

The idea goes back to the German mathematician David Hilbert, who used the example of a hotel to demonstrate the counter-intuitive games you can play with infinity. Suppose that your hotel has infinitely many rooms, numbered 1, 2, 3, etc. All rooms are occupied, when a new guest arrives and asks to be put up. What do you do? It's easy. Ask the guest in room 1 to move to room 2, the guest in room 2 to move into room 3, the guest in room 3 to move into room 4, and so on. If there were only finitely many rooms, the guest in the last room would have nowhere to go, but since there are infinitely many, everybody will find a new abode. You'll have to ask the guests to move simultaneously though, because if you ask them to move one after the other, the move might take an infinite amount of time, since infinitely many guests have to move.

Using this trick you can actually accommodate any finite number of new guests. If $n$ new guests arrive, simply ask each existing guest to move to the room whose number is $n$ plus the number of their existing room. As an example, if there are $8$ new guests, then the guest currently in room $10$ needs to move into room $10+8=18$ .

But things get better still. Suppose an infinite number of new guests arrive, forming an orderly queue outside the hotel. In this case, ask each existing guest to move into the room whose number is twice the number of their current room. So, a guest staying in room $x$ moves to room $2x$ . After this manoeuvre only the even numbered rooms are occupied: rooms $2 = 2 \times 1$ , $4 = 2 \times 2$ , $6 = 2 \times 3$ , and so on. The odd numbered rooms are all free, so you can put your first new guest into room 1, the second new guest into room 3, the third new guest into room 5, and so on. Everybody is happy.

Infinite layering

This isn’t all. Suppose an infinite number of coaches arrive, each carrying an infinite number of new guests. Assume, for simplicity, that the coaches are numbered 1, 2, 3, etc, and that the seats in each coach are also numbered 1, 2, 3, etc. You start by asking each existing guest to move into the room whose number is twice the number of their current room, as before. This leaves the odd numbered rooms free again. Now tell the passenger of coach 1 with seat 1 to move into room 3, the passenger of coach 1 with seat 2 into room $3^2 = 9,$ the passenger of coach 1 with seat 3 into room $3^3 = 27$ , and so on. In other words, the passenger of coach 1 with seat $n$ moves into room $3^ n$ . Any power of $3$ is odd, so all these rooms are guaranteed to be free.

There's room for everyone.

What about people arriving in the second coach? Here’s how to accommodate them: the guest with seat 1 in coach 2 moves into room 5, the guest with seat 2 in coach 2 moves into room $5^2 = 25$ , the guest with seat 3 in coach 3 moves into room $5^3 = 125$ , and so on. In other words, the guest with seat $n$ in coach 2 moves into room $5^ n.$

How do you continue this for the third coach? Well, 3 and 5 are consecutive prime numbers. The next prime number along is 7, so we put the passenger of coach 3 with seat number $n$ into room $7^ n$ . The next prime number after 7 is 11, so we put the passenger of coach 4 with seat number $n$ into the room $11^ n$ . Generally, you put the passenger of coach $m$ with seat number $n$ into the room $p^ n$ , where $p$ is the $(m+1)st$ prime number.

Are all these rooms guaranteed to be free? The answer is yes. All the room numbers of the new guests are powers of prime numbers. There's a beautiful result known as the fundamental theorem of arithmetic, which says that every whole number can be written as a product of primes in a unique way.

This means that if room number $x$ is a power of some prime, then it can’t be a power of another prime. For example, we know that guest number 5 from coach number 1 is allocated room $3^5 = 243.$ Now if there were another guest allocated to the same room, say guest 3 from coach 2, then $x$ would also have to be a power of another prime, eg $x=5^3$ , which, according to the fundamental theorem it can’t be (and isn’t since $5^3=125$ ).

Proof for three layers of infinity

Suppose a guest arrives on ship $s_1$ , coach $m_1$ and seat $n_1$ . This means that she’ll go into room

$q_1^{p_1^{n_1}},$

where $p_1$ is the $(m_1+1)st$ prime number and $q_1$ is the $(s_1+1)st$ prime number. Now suppose another guest, on ship $s_2$ , coach $m_2$ and seat $n_2$ , is allocated to the same room. Then

$q_1^{p_1^{n_1}} = q_2^{p_2^{n_2}},$

where $p_2$ is the $(m_2+1)st$ prime number and $q_2$ is the $(s_2+1)st$ prime number.

By the fundamental theorem of arithmetic, this means that $q_1 = q_2$ and $p_1^{n_1} = p_2^{n_2}$ . Applying the fundamental theorem again shows that the latter implies that $p_1 = p_2$ and $n_1 = n_2.$ Hence the second guest is actually the same as the first.

We’ll carry on for one more level. Suppose an infinite number of ships arrive, each carrying an infinite number of coaches, each carrying an infinite number of guests. Each guest now comes with three numbers attached to them: the number of their ship, the number of their coach and the number of their seat in the coach. You start by moving all the existing guests to the even-numbered rooms as before. Now suppose a guest arrived on ship $s$ , coach $m$ and seat $n$ . We start as before: find the $(m+1)st$ prime number, call it $p$ , and raise it to the power of the seat number. That gives $p^ n$ . Now for the ship number, find the $(s+1)st$ prime number, call it $q$ , and raise that to the number you already have, to get

$q^{p^ n}.$

As an example, if the passenger arrived on ship 1, coach 1 and had seat number 2, then they should move into room

$3^{3^2} = 3^{9} = 19683.$

Numbers get very large very quickly with this approach. The guest from ship $2$ and coach $3$ with seat number $4$ should go into room

$5^{7^4},$

but if you try to work out that number, you’ll find that your calculator will give up. In theory, though, it’s possible to accommodate all the guests (another appeal to the fundamental theorem of arithmetic will prove this, see the box) and since this is maths, theory is all that counts.

So far we have managed to accommodate guests that arrive in three layers of infinity: infinitely many ships, each carrying infinitely many coaches, each carrying infinitely many guests. Can we go further? The answer is yes. You could accommodate guests arriving in any finite number of layers of infinity. What you can't always do, however, is accommodate guests arriving in infinitely many layers of infinity. But then, that's never going to happen anyway.

You can find out more about infinity on our What is infinity? page.

About the author

Marianne Freiberger is Editor of Plus.

Comments

additional band of rooms possible?

Except for the bottom most layer, cant all the layers above it(uptil and including the penultimate layer)start with the first prime number '2' rather than '3'?

If we were to start with 2

If we were to start with 2 rather than 3, then some of the new guests would end up in rooms with even numbers, which are already taken by the existing guests.

Infinite layers

is there somewhere where I can read on how to deal with infinite layers of infinity?

Unknown female.

"This means that she’ll go into room..."
She who? Suddenly one particular female throws the entire argument into a tailspin, but why? If it's important to mention her, then her identidy must be important, but she remains unidentified. Why? Apparently the author doesn't understand the concept and so has to rely on favored speech because without it, she's lost.

Umm

I really hope you're trolling? This proof is just fine.

???

She as in the guest entering the room....

Infinite layers of infinity

What if I had a new coach, where the first passenger is "0", and the last at the back of the bus is "1". In between them, is every real number between 0 & 1. Doesn't this satisfy the "infinitely many layers of infinity" requirement?

No, as #[0,1] is aleph one,

No, as #[0,1] is aleph one, whilst #Z+ is aleph null. I.e. the real numbers are a denser, uncountable infinity. The reason the author says the issue is at infinitely many layers, is because this would be alephnull^2, which is provably aleph one.

To better understand this without needing to understand Cantor’s diagonalisation method, simply ask yourself, if you label the first passenger of your coach 1, then what will the second be labelled? (Remembering, of course, that infinitesimal numbers do not exist in the reals, but rather the Hyperreals and Surreals, and other sets of this nature). Indeed, only the first and last passenger is given an explicit real number, as the reals are not countable and hence not bijective to aleph null.

I believe you mean...

"...is because this would be 2^alephnull, which is provably aleph one."

Review

I do not recommend this hotel.

The check-in process was surprisingly fast and easy, and we went up to our room. I stepped into the bathroom for the usual reasons, and by the time I was done one of the staff was there to inform us that, because an infinitely large bus had arrived, they had to move us to another room.

Which is absurd. Who makes infinitely large buses?

But oh well. They were lying to cover up some mistake. We moved.

An hour later later we moved again.

And every hour or so All. Night. Long.

Finally at 4 AM we gave up and left to look for another hotel. Ended up sleeping in the car.