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.

Lmao

A shorter proof

One of my colleagues sent me the equivalent question, the only difference being the word "bus" instead of "coach" for the vehicle. As the Problem Section Editor of MathAMATYC Educator, I knew of the first two versions, but not the one with infinitely many buses. So, I am using it in an upcoming issue.

Of course, I was not aware that this was online until I talked about it with somebody else, who then sent the link. And that is how I came to be here.

I spent under an hour on solving the "infinite number of buses each with infinitely many people" problem directly. I am not sure how many of my readers (mostly community college math instructors) would care, but my dedication is first to them, not here. Yes, I would love to give it here, as I believe that it is much simpler than what is posted here.

Unfortunately, there seems to be some ethical sense that I would probably have to drop the question from my future column, so I will compromise. If anybody writes me, I will send a short Word 2003 document with solution.

The premise is faulty

I take issue with the premise that "All rooms are occupied." I think it's an invalid premise, and is an example of English syntax not adequately describing maths, especially when infinities are involved.

The only way that something can be true for all members of an infinite set is if it is part of the definition of that set; if we were to say, "Hilbert's hotel has an infinite number of occupied rooms," then it would be valid. But in that case, there would not be room for new visitors; any room we look at is, by definition, full. There can be no shuffling of guests to higher rooms, because those rooms are full too.

If rooms being occupied is not required by the definition, then the statement that "all rooms are occupied" doesn't make sense for an infinite number of rooms. You can't use "all" in that way.

The apparent paradox is, in my view, an illusion caused by the ambiguity of English words. It's like the fallacy of equivocation (https://en.wikipedia.org/wiki/Equivocation), where the same word is used in different ways to give an apparently nonsensical result. "All" doesn't have its usual meaning when applied to an infinite set.

Disagreement on 'the premise is faulty' with Hilbert Hotel

I disagree with Thrawn here. I think the problem is that he does not fully understand the puzzle. Moreover, there actually do exist more formal ways to make the Hilbert Hotel problem more precise. But the problem with what he/ she says is that NOBODY IS SAYING THAT PEOPLE ARE BEING MOVED TO HIGHER ROOMS BEYOND THE EXISTING ONES. In effect, he is arguing against a strawman.

Thrawn has basically made an ipse dixit assertion that something does not make sense. But not making sense can be a limitation on the perceiver, and not necessarily on the message. Although I agree that equivocation can be a problem (e.g., when religious people try to smuggle in the word "faith" for people's confidence or trust in everyday life to argue that faith is useful), it is NOT relevant or applicable here. In the case of the original, much easier Hilbert Hotel problem, one has every room filled and one person comes along. The classic solution to this simpler puzzle is to have each person move to the room with number 1 higher, thus opening up room 1. Nobody is left out in the cold, and there is no "higher number than infinity" type problem that Thrawn seems to worry about.

I reiterate that I will share my solution with anybody who writes me at DrMWEcker@aol.com (that's DrMWEcker at aol dot com). I also will try to remember to come back here to post my solution here AFTER it is published in my column in MathAMATYC Educator.

(Dr. Mike Ecker is a PhD mathematician, a retired math professor, and the problem section editor of the mathematics journal MAE.)