The Joy of X: Solving the Hilbert Hotel Question with Steven Strogatz

  • Thread starter Thecla
  • Start date
  • Tags
    Hilbert
In summary, the conversation discusses the concept of the Hilbert Hotel, a hotel with an infinite number of rooms, and how to assign rooms to an infinite number of guests. It is explained that there is a one-to-one correspondence between rational fractions and hotel room numbers, and that it is possible to make an exhaustive list of all positive fractions even though there is no smallest one. The conversation also touches on the concept of asymptotic density as a measure of hotel occupancy and the possibility of assigning a room to each manager in charge of a specific set of rooms.
  • #1
Thecla
131
10
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.
 
Mathematics news on Phys.org
  • #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.
 
  • #3
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.
 
  • #4
I fixed it, hopefully it should be working now.
 
  • #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.
 
  • #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?
 
  • #8
Thecla said:
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?
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.
 
  • #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?
 
  • Like
Likes micromass
  • #10
MrAnchovy said:
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?
Are you planning on using asymptotic density as your measure of percentage of occupation?
 
  • #11
Yes, that's what it says in the management contract :smile:
 
  • #12
MrAnchovy said:
Yes, that's what it says in the management contract :smile:
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."
 
  • #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?
 
  • Like
Likes pbuk and jbriggs444
  • #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!
 
  • #15
MrAnchovy said:
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?)

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?
 
  • Like
Likes Mentallic
  • #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?
 
  • #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.
Etc.
Where will the guest be after 1 hour?

(Interested people can read up here: https://en.wikipedia.org/wiki/Supertask )
 
  • #18
micromass said:
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?
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.
 
  • #19
jbriggs444 said:
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.

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

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.
 
  • #20
micromass said:
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?

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:
Hyperbolic_Free_Group.png

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.
 
  • Like
Likes pbuk
  • #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 into 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.
 
  • #22
These are excellent (I may have seen some of them before, but they lose nothing for that), but I need to eat first!
 
  • #23
micromass said:
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?
Yes, I still find it beautiful that a series that grows so slowly does not have a finite sum.

micromass said:
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?
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.
 
  • #24
micromass said:
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?

Oh we can't allow that sort of thing, otherwise you are going to end up with this sort of nonsense:

micromass said:
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?

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!
 
  • #25
micromass said:
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.
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.
 
  • Like
Likes micromass
  • #26
micromass said:
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:

...

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-Cohen [edited].

That reminds me of the way we lay out the buffet so that everyone gets a whole fish for dinner:

Escher_Circle_Limit_III.jpg


We cover 1-3 in basic manager training, but the Standard Operating Procedures don't cover 4. For a long time there was an argument within the hotel group about whether it was actually possible to build a hotel like your Hotel Gödel-Cohen with more rooms than Hotel Hilbert but not as many as Hotel Cantor so we drafted two sets of SOPs, one declaring that it was possible and one declaring that it wasn't. But do you know what? It doesn't actually matter!
 
  • #27
MrAnchovy said:
We cover 1-3 in basic manager training, but the Standard Operating Procedures don't cover 4. For a long time there was an argument within the hotel group about whether it was actually possible to build a hotel like your Hotel Gödel-Cohen with more rooms than Hotel Hilbert but not as many as Hotel Cantor so we drafted two sets of SOPs, one declaring that it was possible and one declaring that it wasn't. But do you know what? It doesn't actually matter!

But then there are many different SOPs! One saying there is no Gödel-Cohen Hotel. One saying that there is (essentially) exactly one Gödel-Cohen Hotel. One saying there are (essentially) two, etc.
So we get to
5) How many possible SOP's are there? Is it possible to lay an SOP in every room of the Hilbert Hotel (with possibly multiple SOP's in a room).
 
  • #28
micromass said:
But then there are many different SOPs! One saying there is no Gödel-Cohen Hotel. One saying that there is (essentially) exactly one Gödel-Cohen Hotel. One saying there are (essentially) two, etc.
So we get to
5) How many possible SOP's are there? Is it possible to lay an SOP in every room of the Hilbert Hotel (with possibly multiple SOP's in a room).
Thanks micromass, you have moved me right out of my comfort zone and I've had to go back to my notes; I have come to a halt because I have never fully grasped forcing and I need to do some practice.

Now in our hotel group we have actually come to rely on the idea that there is no hotel larger than the Hilbert and smaller than the Cantor - we call this concept "CH" (some people think this stands for Cantor Hotel but of course it doesn't), so although CH isn't actually part of our SOPs we kind of assume it's true. We sponsor quite a lot of research in this area including some by, believe it or not, the guy that designed the carpet in the hall, but to be honest it's all a bit over my head so I'm really not sure about your question 5 - although it's not official I work by my own copy of the SOPs where I've replaced "C" with "GCH" which rules out any Gödel-Cohen Hotels (and no, GCH does not stand for Gödel-Cohen Hotels either).
 

1. What is the Hilbert Hotel Question?

The Hilbert Hotel Question is a thought experiment that was created by mathematician David Hilbert in the early 1920s. It poses the question of whether it is possible to accommodate an infinite number of new guests in a hotel with an infinite number of rooms, if all the rooms are already occupied.

2. Who is Steven Strogatz?

Steven Strogatz is an American mathematician and professor at Cornell University. He is known for his work in nonlinear dynamics and complex systems, and has written several books on mathematics, including "The Joy of X".

3. What is "The Joy of X" about?

"The Joy of X" is a book that explores various concepts in mathematics and presents them in a way that is accessible to non-mathematicians. It covers topics such as geometry, algebra, calculus, and more, using real-world examples and anecdotes to make the subject more relatable.

4. How does "The Joy of X" solve the Hilbert Hotel Question?

In the book, Steven Strogatz presents a solution to the Hilbert Hotel Question by using the concept of infinite sets and cardinality. He explains how, even though there may be an infinite number of guests and rooms, there are different levels of infinity and it is possible to rearrange them in a way that allows for the infinite number of new guests to be accommodated.

5. Is "The Joy of X" suitable for non-mathematicians?

Yes, "The Joy of X" is written in a way that is easy for non-mathematicians to understand. The book uses everyday examples and analogies to explain complex mathematical concepts, making it an enjoyable and informative read for anyone interested in the subject.

Similar threads

Replies
8
Views
1K
Replies
69
Views
5K
  • General Math
Replies
22
Views
2K
Replies
31
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
  • General Math
Replies
5
Views
2K
  • Quantum Physics
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
8K
  • General Math
Replies
1
Views
3K
Replies
89
Views
21K
Back
Top