Add new comment

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.

Plus.Maths.org

Hilbert's hotel

Infinite layering

Proof for three layers of infinity

About the author

Filtered HTML