A big, big, big hotel

[harey]

There is a hotel with an infinite number of rooms, all rooms occupied by little green men (one man in a room). An infinity of little blue man arrive and each one asks for a room. No problem, the manager moves the blue man from the room n to the room 2*n, freeing the odd-numbered rooms for the green men. So far, loosely copied from https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel.

It turns out that the blue men sing between noon and midnight and sleep between midnight and noon while the green men sleep between noon and midnight and sing between midnight and noon. Complaints.

The manager decides to group them. Conveniently, the rooms are in a straight line, numbered from left to right. While there is a green man left to a blue man, he makes them change the rooms.

Eventually, all the blue men leave.

- how many rooms are free?
- how many rooms remain occupied?
- what is the number of the first occupied room?

[bonanova]

OK I think I just found your first blue man.

Spoiler

If a process can be reduced to an algorithm (a program) that involves no more than countably infinite steps, then the process can be carried out in finite time. At least in theory. But that's sufficient to at least discuss the consequences or effect of the process.

We can do a process with countably infinite steps in finite time by scheduling step_i at a time t_i = 1/2ⁱ minutes before midnight. The steps are executed at times 1, 1/2, 1/4, 1/8 ...., 1/2ⁱ, .... and the process completes in one minute. But what if we wanted to run a (countably) infinite number of such processes. Can we also do that?

Well, the universe will freeze in less than countably infinite minutes. But we can run each successive process in half the time of the previous one and finish everything in finite time. So, Yes, we can do that.

Spoiler

Let process₁ begin at 2 minutes before midnight and run its steps at these times thereafter { 0 1/2 1/4 1/8 ... } as before, and now end at 1 minute before midnight, at which time process₂ begins. We run its steps at these times thereafter 1/2 x { 0 1/2 1/4 1/8 ... }, so that it ends at 1/2 minutes before midnight, at which time process₃ begins, subsequently ending at 1/4 minutes before midnight. In general, process_j will begin at 1/2^(j-1) minutes before midnight with steps executed at times 1/2^j x { 0 1/2 1/4 1/8 ... } thereafter, and compete at 1/2^j minutes before midnight. At midnight then, a countably infinite number of processes, each with a countably infinite number of steps will have completed. And as before the j^th step of the i^th process has a unique and unambiguous execution date. So now we can do processes of complexity O(N²) on countably infinite sets. That is another way of saying that { Aleph₀ }² = { Aleph₀ }. To get to a higher order of infinity you need 2^{{ Aleph₀ }}.

Now lets revisit Hilbert's Hotel and write some algorithms:

We have 3 countably infinite sets: { r = rooms } { b = blue men } { g = green men } and a bunch of things to do. Let's list them.

1. Place b_i in r_i. Blue men have all checked in.
2. Evacuate all rooms. Sorry to bother you, but some green men want to check in.
3. Place b_i in r_2i. Check Blue men into even-numbered rooms
4. Place g_i in r_2i-1. Check Green men into odd rooms, so it's g b g b g b g b g b ....
   
   All these are O(N) processes, which we know we can do.
   But now we want to sort the occupants, using a type of bubble sort,
   which is an O(N²) complexity process. But hey, we just showed how to do that, as well.
    
5. For all j run process_j consisting of
6. For all i if b(r_i) and g(r_i+1) then swap those room occupants

At this point the clock has struck midnight and the horrific job is done. There is now no blue man in a room that has a lower number than a room occupied by a green man.

What have we accomplished? We'd like to say that in a countably infinite linear array of rooms we have placed a countably infinite set of green men, followed by* a countably infinite set of blue men. We know that we have enough rooms, because our rooms accommodated these same men when they were initially interleaved, all of which is to say

SizeOf ( { rooms } )  =  SizeOf ( { green men } )  +  SizeOf ( { blue men } )  =  Aleph_0.

So let's note here that Aleph₀, the cardinality (SizeOf) of the counting numbers, is unchanged by "multiplying it by," or even "raising it to," any finite number. Those words are in quotes because Aleph₀ is not a number and it does not follow the rules of algebra. But now at least we should hear an alarm bell and see a flashing red light if we try to say things like inf+1 or 2xinf or the like. These are not numbers, either.

But can we say anything more about the room assignments? For example initially a blue man was sleeping in Room₂. And now we know (just by examining the doubly-infinite set of steps described in lines 5 and 6) that man is soundly asleep, hopefully, in a different room. Presumably he could open his door and read his room number. If we had a really long string with tin cans on the ends we could ask him what it is. How would he answer? Well since { rooms } = { green men } + { blue men } and he is the first blue man, he'd have to say "My room number is ... Aleph₀ + 1." What a prestigious address -- like the ultimate penthouse. Wow. There we have it. But what we have is meaningless.

So anyway I was wrong before. We can, by following a well-defined procedure, place all the blue men after* all the green men. But after we've done it, we've lost track, in conventional terms, of their room numbers. Other than to say "they're waaaaaay out there, unspeakably greatly removed from the hotel office." And so much for room service! I think we can say that the blue men originally in rooms 2 and 4 are now neighbors, but maybe we can't even say that. It would be like asserting that (inf+2) - (inf+1) = 1, where the terms on the left are meaningless. Maybe we can just say the blue room numbers are all infinitely large. But maybe we can do better than that, in a different way?

Spoiler

* Except that followed by, and after, etc., imply this completion thing again.

We handled the completion of infinite events by clever scheduling. So let's take a page from that playbook so that I can do a better job of describing the new location of the first blue man.

Hilbert's hotel undergoes a re-design:

Room₁ is now its most luxurious room with a colossal width of 1 mile. Room₂ less grand, but certainly nothing to sneeze at, weighs in at a comfortable width of 1/2 mile. Room₃ is "only" 1/4 mile wide. Similarly, each Room_i has a width of precisely 1/2ⁱ miles. Thus a countably infinite number of HH rooms fits alongside a workable 2-mile-long parking lot. Let's paint this building a refreshing sea green, and into its rooms let's place all the { green men }. Immediately adjacent to that building lies another set of rooms, the first of which is, again, 1 mile in width. Next to it is a 1/2-mile-wide room, followed, in turn, by rooms 1/4, 1/8, ... miles wide. They comprise a second 2-mile-wide building, which we will paint a lovely azure blue and into whose rooms we now place all of the { blue men }.

If all the rooms are numbered consecutively we still do not know the number of the first blue man's room. But if we want to visit him we can look at a map and clearly locate it! We only have to walk 2 miles from the office. Or we can simply jog down to the blue building, and knock on its first door. Hi, mister first blue man, nice to see you.

How's that?

 

[bonanova]

Spoiler

Still waiting for the blue and green men to switch rooms. Check back later. (Much later.)

I have a hunch that the required room swaps are not countably infinite. But if they are, if the swaps can be described in sequence order and associated 1-1 with the integers, then we might schedule them to complete in finite time by scheduling the swaps to occur at 1, 1/2, 1/4, 1/8, ..., 1/2^n, .... minutes before midnight. And then the questions could be asked, and it would be fun to consider their possible answers.

Otherwise it's akin to find a reordering of the integers that places all the even integers after the "end" of all the odd ones. That place does not exist; there is no "final" odd integer. The last question seems to ask for a finite value of N as N -> inf. What is the (finite) room number for a room that lies infinitely far from Room 1? There is no finite number that associates with infinity.

 

[harey]

20 hours ago, bonanova said:

How's that?

Brilliant, surprisingly interesting and leading to a major annoyance.

Spoiler

I did not expect much from this question, it is not a number, basta. I had the idea to number the rooms of the green men starting with 1, but had to find a different 1 from the 1 of the room number of the first green man.  And I did not do the jump. Seems so easy now. But...

An infinity of rose women arrives. Each woman is married to one and only one blue or green man and each man is married to exactly one woman. Each woman asks for a separate room adjacent to her husband's room. The manager understands 'adjacent' his way and instead of moving people, he builds a 2nd floor. Each woman is therefore upstairs her husband. There is a relation 1 to 1 between integers and women, their rooms can be numbered the conventional way. Now a woman complains the wives of blue men have the same room number as their husbands while she does not. Telling her that blue numbers and rose numbers are different seems a little week.

I think we can say that the blue men originally in rooms 2 and 4 are now neighbors, but maybe we can't even say that. It would be like asserting that (inf+2) - (inf+1) = 1, where the terms on the left are meaningless.

Oh yes, we can say that. The blue man from the room 2 * n (original numbering) is now now in the room n_blue. Same for the green men. True for any n, if true for n then true for n + 1, why not for n -> inf? The equation does not bother me as long as we interpret it the same way:
(2 miles down + 2) - (2 miles down + 1) = 1. (There might be a restriction: it is true in this problem, but it might be meaningless in other circumstances.)

Another way to write it:
(11_blue - 5_blue)=(71_green - 65_green). In both cases, there are 6 walls between them, too much to communicate via WiFi.

Well, now back to the original problem. Everybody leaves, the hotel is empty. The green and blue men arrive all together and go to the room they occupied previously. Is this problem equivalent to the first one?

Precision: By equivalent, I mean that the problems are announced in a slightly different way, but the answers remain the same. Something this way:

Aunt: If I give you 5 bananas and take back 2 bananas, how many bananas have you?
John: I do not know.
Aunt: I met your teacher and she told me you make this kind of problems at school.
John: Yes, but we do it with apples.

Just do not tell me that the men know now the room numbers. Besides being clairvoyant, they can move in time. Forwards, backwards and sideways.

Edited February 24, 2018 by harey
Some cosmetics to make it easier to read.

[bonanova]

On 2/24/2018 at 3:42 AM, harey said:

Brilliant, surprisingly interesting and leading to a major annoyance.

Yeah, I hate annoyances, too...

Spoiler

This discussion has been a challenge to sharpen my thinking, and my words. And it has been fun. Thanks for that.

Meantime, I recalled the problem of proving that the rationals, { p/q } for integers p and q, are countable. By definition { integers } are countable. And so { p } and { q } individually are countable. But can we establish that { all pairs of p and q } are countable? This was doubted at one time, but in fact they are: { pairs of p and q } can be matched 1-1 with { integers }. However, care must be taken in constructing the proof.

One failed proof first counts { 1/q }, then counts { 2/q }, then { 3/q }, and so on. But there is a problem with this. Once { 1/q } has been counted, we're done counting! Every element of { 1/q } matches to an integer, but every integer points to an element of { 1/q }. Ouch. That leaves { 2/q }, { 3/q }, .... uncounted. Matching two infinite indexes to the integers is a little tricky. It can be done, but it takes a bit of cleverness. If you haven't seen that proof, you can read it here. Fun to recall. Now back to the Hotel.

Let's combine the infinite sets { blue men } and { green men } into the set { men } and try to prove that { men } is countable. We need to find an integer for each man, and a man for each integer. That is, we need to find a bijection between { men } and { integers }: But wait. If we think of { rooms } as { integers } this is precisely our room assignment task: to find a bijection between { men } and { rooms }. And we should be careful in creating it, recalling the failed attempt regarding rational numbers. Some schemes may succeed, but clearly not every scheme.

In fact, one way to fail is to first assign rooms to the green men. That fails because it only serves only to create a bijection of { rooms } with { green men }. Every green man gets a room, true, but (gulp) also, every room houses a green man. Oy vey! The blue contingent got excluded. Yes -- we see them now, trudging down the road to the Holiday Inn. Want their room numbers? Call HI.

But we can house { men } at HH, interleaved. And also prove { men } is countable: just read their room numbers.

That's the crux, I think, of all the matters we've discussed.

 

[harey]

15 hours ago, bonanova said:

In fact, one way to fail is to first assign rooms to the green men. That fails because it only serves only to create a bijection of { rooms } with { green men }. Every green man gets a room, true, but (gulp) also, every room houses a green man. Oy vey! The blue contingent got excluded.

 

I do not think there is need to use the spoiler anymore.

If the blue are excluded because every room houses a green man, the same way you cannot accept even a single new guest.

[bonanova]

15 hours ago, harey said:

If the blue are excluded because every room houses a green man, the same way you cannot accept even a single new guest.

Precisely.
 

If every room houses a green man, new customers have no place to sleep.

This does not work: { g1 g2 g3 ... gi .... b1 } <=> { r1 r2 r3 ... ri .... rinf+1 }  
 

Do we want another guest?  We can't assign gi to ri.

This does work: { b1 g1 g2 g3 ... gi .... } <=> { r1 r2 r3 r4 ... ri+1 .... }  gi is no longer in ri.