1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hilbert Hotel Question

  1. Aug 14, 2015 #1
    In "The Joy of X" Steven Strogatz discuss in a chapter on the Hilbert Hotel,a hotel with an infinite number of rooms, the problem of assigning rooms when an infinite number of buses arrive, and each bus has an infinite number of passengers. "There is always room at the Hilbert Hotel" says the manager and Steven Strogatz describes how it is done. Every guest has a room. For exampe bus#45 passenger #77 goes in a certain room.

    The bus number and passenger number (p, q) represent a rational fraction p/q.There is a one to one correspondence between p/q and hotel room number,the set of integers.

    Mr. Strogatz says that we can make an exhaustive list of all positive fractions(rational numbers) even though there is no smallest one.
    Arranging all the integers from one on up I can understand, but I have a hard time in the opposite direction.
    Even though there is no smallest rational number, he says you can make an exhaustive list of all positive fractions.

    How do you do this ? All integers I can understand, but going in the other direction toward Zero I can't see how an exhaustive list can be made.
  2. jcsd
  3. Aug 14, 2015 #2
    Are you asking for a proof there exists a bijection or for an explicit sequence?

    If it is the first case, there is a simple bijection from [itex]f:\mathbb Q_+\rightarrow\mathbb N\times\mathbb N[/itex] where ## f(\frac{p}{q})=(p,q) ##. Then you can find some bijection ## g: \mathbb N \times \mathbb N \rightarrow \mathbb N## since the cartesian product of countable sets is countable, and simply form a composition ##g \circ f: \mathbb Q_+ \rightarrow \mathbb N ##.

    If you are asking for a listing, there is a very neat picture in the link that follows: http://www.charlesgao.com/wp-content/uploads/2009/03/rational_diagnal.jpg

    It is easy to see that every positive rational is in that list, and you can count them by starting at ##\frac {1}{1}## and following the arrows as shown.
  4. Aug 14, 2015 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Well, it seems that if you take the set of all the natural numbers, N = 1, 2 , 3, ..., you can write a set of positive fractions of the form 1/N, and another set 2/N, and so forth.

    All such sets (with the obvious exclusion of the fractions N/N) would form the set of all positive fractions.

    I think here you are confusing "fraction" to mean any rational number, such as 1 / 2.345 for example.

    Unfortunately, Mirero's link seems to be disabled.
  5. Aug 14, 2015 #4
    I fixed it, hopefully it should be working now.
  6. Aug 14, 2015 #5
  7. Aug 15, 2015 #6
    There is no reason to work with rational numbers here. Just working with pairs is enough. So ##(p,q)## represents passenger ##q## on bus ##p##. Sending this passenger to room ##2^p 3^q## gives every passenger a different room. For example, passenger ##5## on ##4## goes to room ##2^4 3^5 = 3888##.
    Note that in this way, not all the rooms will be filled. For example, room ##5## will not get anybody.
  8. Aug 15, 2015 #7
    Thanks for the help MrAnchovy. I did not know that there was an orderly way to create ALL possible fractions( what we called proper and improper fractions). Micromass, Will any pair of prime numbers(you used 2,3) be able to assign rooms to all the guests?
  9. Aug 15, 2015 #8


    User Avatar
    Science Advisor

    Yes, any pair of prime numbers will work. Any pair of relatively prime numbers will work. In fact, almost any pair of integers that are both greater than 1 will work. You just have to avoid cases where the prime factorization of the two numbers has the same prime factors in the same proportions. e.g. 4 and 8 (prime factorization is all 2's) or 6 and 36 (prime factorization is a 50/50 mix of 2's and 3's).

    2 and 3 just happen to be convenient and small and it is obvious that no [strictly positive] integer power of the one can be equal to an integer power of the other.
  10. Aug 15, 2015 #9
    micromass and jbriggs444 may think they are doing a good job as hotel managers fitting in all those guests, but I own a chain of hotels which include these two and every week I look at the occupancy figures to make sure the hotels are being well managed. Occupancy is the proportion of available rooms that are occupied, so if an hotel has 100 rooms and 90 are occupied then occupancy is 90% - which happens to be my target: if a manager regularly falls below that they are likely to be sacked.

    So what is the occupancy of a hotel where, for instance, only every even numbered room is occupied? What about micromass's and jbriggs444's hotels? How about Mirero's?
  11. Aug 15, 2015 #10


    User Avatar
    Science Advisor

    Are you planning on using asymptotic density as your measure of percentage of occupation?
  12. Aug 15, 2015 #11
    Yes, that's what it says in the management contract :smile:
  13. Aug 15, 2015 #12
    Actually I just checked the contract, it says "The occupancy for any night shall be the lower asymptotic density of the rooms with paying guests for that night."
  14. Aug 15, 2015 #13
    Another question: every collection of rooms in the hotel has a manager. There is of course the big manager who manages all the rooms. But there is also the "even manager" who manages all the even rooms, and the "odd manager". There is also a manager in charge of room 17 specifically. There is a "prime manager" and there is a manager in charge of room 2,3,6 and 2000. There is also a "lazy manager" in charge of no room at all! Every collection of rooms has a manager.

    Can you let each and every manager stay in a room? That is, is can you assign a room to each manager so that no two managers share a room?
  15. Aug 15, 2015 #14
    I love Hilbert's hotel - it is accessible to anyone regardless of their mathematical background but it can be extended to introduce many concepts (e.g. it takes 1 hour to clean room 1, 1/2 h for room 2, 1/4 h for room 3: how long does it take to clean the whole hotel?)

    But congratulations micromass, that's the first time I've seen a extension to power sets!
  16. Aug 15, 2015 #15
    It takes 1 hour to clean room 1, 1/2 hour to clean room 2, 1/3 hour to clean room 3, 1/4 hour to clean room 4, etc. How long does it take to clean the whole hotel?

    Or this: it takes 1 hour to clean room 1, 2 hours to clean room 2, 3 hours to clean room 3, etc. Show that it takes -1/12 hours to clean the whole hotel. What?
  17. Aug 15, 2015 #16
    I have two infinity hotels, say "Hotel Hilbert" and "Hotel Cantor". At the start, Hotel Hilbert is occupied completely, while Hotel Cantor is completely empty. Residents of Hotel Hilbert are given a card which specifies their room numbers (so resident of room 77 gets card which says 77). They will keep this card through the entire process and they will not lose it.

    After 1 hour, I take the inhabitants with card 1 and 2 of Hotel Hilbert and move them to Hotel Cantor.
    1/2 hour after that, I first take the inhabitants with card 3 and 4 of Hotel Hilbert and move them to Hotel Cantor, then I will take the inhabitant with card 1 of Hotel Cantor and kick him out.
    1/4 hour after that, I first take the inhabitants with card 5 and 6 of Hotel Hilbert and move them to Hotel Cantor, then I will take the inhabitant with card 2 of Hotel Cantor and kick him out.
    1/8 hour after that, I first take the inhabitants with card 7 and 8 of Hotel Hilbert and move them to Hotel Cantor, then I will take the inhabitant with card 3 of Hotel Cantor and kick him out.
    I repeat this process.

    After 2 hours. Prove:
    1) Hotel Hilbert is empty.
    2) Hotel Cantor is empty.

    But how can (2) be correct if at each step, the net effect was to add a resident to Hotel Cantor. So adding a resident each step somehow makes the Hotel empty?
  18. Aug 15, 2015 #17
    If the previous is too difficult to get, consider the following:

    I have a completely empty Hotel Hilbert. A guest arrives and I put him in room 1.
    After 1/2 hour, I move the guest to room 2.
    After 1/4 hour, I move the guest to room 3.
    After 1/8 hour, I move the guest to room 4.
    Where will the guest be after 1 hour?

    (Interested people can read up here: https://en.wikipedia.org/wiki/Supertask )
  19. Aug 15, 2015 #18


    User Avatar
    Science Advisor

    The quick answer is that the cardinality of a limit is not neccessarily equal to the limit of the cardinalities.

    Casting the problem in terms of hotels tends to gloss over the fact that we are dealing with limits.
  20. Aug 15, 2015 #19
    I understand your reasoning, and it is very plausible. But I don't agree with it.
    In my opinion, the correct answer is that the entire notion of a supertask (= performing infinitely many tasks in a finite time) is just impossible, both physically in the real world (of course), as logically in a made up world.
    To argue this, I propose a lamp which was switched on at time 0.
    At time 1/2, I switch the lamp off.
    1/4 after that, I switch the lamp on.

    Will the lamp be on or off at 1? Clearly, the problem is just ill-posed. The other things I linked are ill-posed in the same manner. There is no way to do infinitely many things, and there is no reasonable thing we can say about the "limit".

    This means a lot to mathematics, since it limits mathematics to things we can only do in finitely many steps. And indeed, although mathematics can deal with the infinite, every infinite concept is described in terms of steps that are finitely checkable.
  21. Aug 15, 2015 #20
    To expand on this. We first take "Hotel Hilbert" which just has infinitely many rooms, each room being numbered with a (positive) integer.
    We take another hotel "Hotel Cantor" of the following form:
    In Hotel Cantor, all the points on the black circle are rooms. To get to a room, you start from the center (the entrance of the hotel). Then you follow the red and blue arrows depending on what your room is. For example, if the coordinates of your room start with aabb, then
    You first go right, taking the red arrow.
    You go right again, taking the red arrow.
    You go up, taking the blue arrow.
    You go up again, taking the blue arrow.

    Thus every room has a room number which is an infinite sequence of a's and b's.

    Show the following:
    1) The managers of Hotel Hilbert can be resided completely in Hotel Cantor, and they can fill up Hotel Cantor.
    2) If Hotel Hilbert is completely filled, then it is possible to move everybody from Hotel Hilbert to Hotel Cantor. But it is not possible to do this in a way that Hotel Cantor will be completely full (if it was initially empty).
    3) If Hotel Cantor is completely filled, then it is impossible to move everybody from Hotel Cantor to Hotel Hilbert.
    4) Find a Hotel Gödel-Cohen such that A) It is impossible to move everybody from Hotel Gödel-Cohen to Hotel Hilbert, and B) It is impossible to move everybody from Hotel Cantor to Hotel Gödel-Cantor.
  22. Aug 15, 2015 #21
    Hilbert's hotel is a fallacy. The problem is there is always some one in the hallway. To convince yourself this is true try to check in to Ramsey's hotel. Ramsey's hotel has a hallway with a finite size. It connects to an infinite number of rooms in an infinite number of dimensions. Move some one out of a room into the hallway then you can move some one else into that room but there is still some one in the hallway. In Hilbert's hotel moving 1 additional person in the hotel will always result in 1 person being in the hall at any one time. Moving an infinite number of additional people into the hotel will always result in an infinite number of people in the hallway at any given time.
  23. Aug 15, 2015 #22
    These are excellent (I may have seen some of them before, but they lose nothing for that), but I need to eat first!
  24. Aug 15, 2015 #23
    Yes, I still find it beautiful that a series that grows so slowly does not have a finite sum.

    We have a set of standard operating procedures in my hotel group - they are arbitrary, but consistent (although there are some situations that they just don't seem to cover). Manipulation of the sort that you need to get that result is outside the SOPs.
  25. Aug 15, 2015 #24
    Oh we can't allow that sort of thing, otherwise you are going to end up with this sort of nonsense:

    We have to be really careful about how we match people up to rooms, and supertasks are specifically outlawed in the SOPs, although I seem to remember it was quite hard to get the drafting right - we had to change it after Mr and Mrs Zeno came to stay: Mr Zeno was quite slow on his feet so he set off down the corridor while his wife signed the register and picked up the keys before haring off after him but we had to refund their stay because she never managed to catch him up!
  26. Aug 15, 2015 #25


    User Avatar
    Science Advisor

    I do not disagree with this at all. That is the stance that I prefer as well. But I am willing to speak as if those supertasks for which a limit exists have a result that matches what is prescribed by that limit.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook