Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Hilbert's hotel

      Marianne Freiberger
      13 February, 2017
      14 comments

      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.

      Hotel

      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×1, 4=2×2, 6=2×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 32=9, the passenger of coach 1 with seat 3 into room 33=27, and so on. In other words, the passenger of coach 1 with seat n moves into room 3n. Any power of 3 is odd, so all these rooms are guaranteed to be free.
      Hotel keys

      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 52=25, the guest with seat 3 in coach 3 moves into room 53=125, and so on. In other words, the guest with seat n in coach 2 moves into room 5n. 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 7n. The next prime number after 7 is 11, so we put the passenger of coach 4 with seat number n into the room 11n. Generally, you put the passenger of coach m with seat number n into the room pn, 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 35=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=53, which, according to the fundamental theorem it can't be (and isn't since 53=125).

      Proof for three layers of infinity

      Suppose a guest arrives on ship s1, coach m1 and seat n1. This means that she'll go into room q1p1n1, where p1 is the (m1+1)st prime number and q1 is the (s1+1)st prime number. Now suppose another guest, on ship s2, coach m2 and seat n2, is allocated to the same room. Then q1p1n1=q2p2n2, where p2 is the (m2+1)st prime number and q2 is the (s2+1)st prime number. By the fundamental theorem of arithmetic, this means that q1=q2 and p1n1=p2n2. Applying the fundamental theorem again shows that the latter implies that p1=p2 and n1=n2. 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 pn. 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 qpn. As an example, if the passenger arrived on ship 1, coach 1 and had seat number 2, then they should move into room 332=39=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 574, 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.

      • Log in or register to post comments

      Comments

      Neel

      8 March 2017

      Permalink

      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'?

      • Log in or register to post comments

      Marianne

      10 March 2017

      In reply to additional band of rooms possible? by Neel

      Permalink

      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.

      • Log in or register to post comments

      Miguel Cruz

      1 May 2018

      Permalink

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

      • Log in or register to post comments

      Caoimhin Connell

      6 September 2018

      Permalink

      "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.

      • Log in or register to post comments

      KP

      12 April 2019

      In reply to Unknown female. by Caoimhin Connell

      Permalink

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

      • Log in or register to post comments

      Zeid

      8 May 2019

      In reply to Unknown female. by Caoimhin Connell

      Permalink

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

      • Log in or register to post comments

      Fred

      18 January 2021

      Permalink

      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?

      • Log in or register to post comments

      Anonymous

      4 March 2021

      In reply to Infinite layers of infinity by Fred

      Permalink

      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.

      • Log in or register to post comments

      Anonymous

      23 September 2021

      In reply to No, as #[0,1] is aleph one, by Anonymous

      Permalink

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

      • Log in or register to post comments

      Don Edwards

      21 April 2022

      Permalink

      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.

      • Log in or register to post comments

      Luca

      8 December 2022

      In reply to Review by Don Edwards

      Permalink

      Lmao

      • Log in or register to post comments

      Dr. Michael W. Ecker

      18 August 2023

      Permalink

      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.

      • Log in or register to post comments

      Thrawn

      5 September 2023

      Permalink

      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.

      • Log in or register to post comments

      Dr. Michael W. Ecker

      10 January 2024

      In reply to The premise is faulty by Thrawn

      Permalink

      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.)

      • Log in or register to post comments

      Read more about...

      infinity
      Hilbert's hotel
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms