## Hilbert's Hotel...continued

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### Hilbert's Hotel...continued

Hilbert's Paradox of the Grand Hotel, just to recap before I get to the point, goes as follows:

There is a hotel with an infinite number of rooms, and on one particular night, all its rooms are occupied with one guest. On that night, a guest shows up. How can we accommodate this guest, when the hotel is full? We can ask our guests to move, but this must take a finite amount of time, and there must be only one guest to a room. There is more than one answer.

The answer (one answer) is spoiler'd for those who haven't seen this problem, and for organization.
Spoiler:
One solution is simply to tell every guest to move up one room, and give the newcomer the first room.

In another words, we supply every current guest with a function, in this case, f(n)=n+1. Each guest moves to room f(n), where n is their room number. We give the new guest the number 1 (the first room).

That was the easy part (one of them). Now, let's say that just as our guests are finished unpacking their things in their new rooms, a bus with an infinite number of passangers pulls up to the hotel. The question is, using the same rules as before, how do we supply all the passangers on the bus with a room?

Spoiler:
We tell all our current guests to occupy the even numbered rooms (2n), and our new guests to occupy the odd numbered rooms (2n+1), where n is a guest's room number, or a passanger's seat number (both starting at 1).

The last part is the same except instead of one bus, there's an infinite number of buses.

Spoiler:
Every bus is said to have a number, m. The hotel is regarded as bus 0. The function that we give every person is f(m,n)=p(n)^n, where p(n) is the nth prime number, and n again is seat number.

My question is why stop there? What if an infinite number of (rows?, columns?, caravans?), each containing an infinite number of buses, each containing an infinite number of passangers, shows up at the hotel?

I guess the problem is to come up with an injective (not necessarily bijective) function from N(all natural numbers, starting with 1, I suppose)^3 to N, where the last problem was to come up with an injective function from N^2 to N.

Obviously (I think), the next step would be to come up with an injective function from N^4 to N, and so on ad infinitum. How about N^n onto N? Then what (assuming the steps up to this point are even possible)?

EDIT: So, for now, can anyone come up with a solution to the fourth part? Also, is there a bijective solution to part three (like part one and two, leaving no empty rooms)?

EDITEDIT: Would this be better off in the Mathematics forum?
Last edited by afarnen on Fri Mar 06, 2009 11:12 pm UTC, edited 2 times in total.
afarnen

Posts: 157
Joined: Mon May 05, 2008 12:12 pm UTC

### Re: Hilbert's Hotel...continued

Trivial solution:
Spoiler:
Suppose you have a function f(m, n) that maps from NxN to N. For Nx, simply apply it x-1 times. So, for N5 you'd have f(f(f(f(a, b), c), d), e).
douglasm

Posts: 499
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Hilbert's Hotel...continued

EDIT: I'm not sure if that's even possible, or mathematically valid.
afarnen

Posts: 157
Joined: Mon May 05, 2008 12:12 pm UTC

### Re: Hilbert's Hotel...continued

afarnen wrote: I'm not sure if that's even possible, or mathematically valid.

You're talking about Hilbert's Paradox. Mathematics probably shrugs its proverbial shoulders and gives up around the "infinite hotel that's also full" part.

6453893

Posts: 556
Joined: Wed Dec 13, 2006 2:40 am UTC
Location: Australia

### Re: Hilbert's Hotel...continued

EDIT: I'm not sure if that's even possible, or mathematically valid.

It is mathematically valid. It is also an uncountable infinite and therefore cannot be fit into the Hotel no matter what you do. Any finite number of layers can be packed in, but taking that exponent to infinite crosses the line into uncountability.
douglasm

Posts: 499
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Hilbert's Hotel...continued

If you have an infinite number of buses, each with an infinite number of compartments, each with an infinite number of subcompartments, each of THOSE having an infinite number of compartments, going forever, with one customer in each "infinitieth" compartment, then you can think of each new guest as corresponding to an infinite sequence of integers. In this case you can't fit them into the hotel.

However, if each guest lives in a compartment at some finite stage (so there's a driver for each bus, a passenger plus an infinite number of subcompartments in each compartment, another passenger with another infinite number of subcompartments in each subcompartment, etc.) and no passengers at the "infinitieth" level, you CAN fit them in the hotel. If what I've said makes any sense, try it out!

On the other hand, even if only two buses show up and there's just two subcompartments at each stage, so each passenger corresponds to an infinite sequence of just one's and two's, you can't fit them in the hotel. I hear the reason is big, gray, and proves uncountability of the reals.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

Posts: 648
Joined: Sat Oct 27, 2007 5:51 pm UTC

### Re: Hilbert's Hotel...continued

6453893 wrote:You're talking about Hilbert's Paradox. Mathematics probably shrugs its proverbial shoulders and gives up around the "infinite hotel that's also full" part.
Wait, what?
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

antonfire

Posts: 1770
Joined: Thu Apr 05, 2007 7:31 pm UTC

### Re: Hilbert's Hotel...continued

afarnen wrote:We can ask our guests to move, but this must take a finite amount of time

Doesn't this invalidate the solutions you've given to all but the first part?

Spoiler:
Moving each existing guest from room n to room 2n can't be done in any finite span of time.
Chuff wrote:I write most of my letters from the bottom

Goldstein

Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

### Re: Hilbert's Hotel...continued

I believe he means that it must take a finite amount of time for each guest to move, not for all guests to be moved. Basically this just rules out solutions like "Tell all the current guests to start walking down the hall, and then fill in the rooms as they leave them" because there is no set time when the guests that have left their rooms will enter another room.

quintopia

Posts: 2790
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### Re: Hilbert's Hotel...continued

Ah. Fair enough.

You could also have called me on my above assertion not being true! I think even the third situation (Infinitely many individuals on each of infinitely many buses) can see all existing guests moved to their new rooms within a bounded span of time, though it's another matter altogether, and clearly impossible, to get the new arrivals into their rooms in a finite time.
Chuff wrote:I write most of my letters from the bottom

Goldstein

Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

### Re: Hilbert's Hotel...continued

Hilbert’s Hotel is a (hypothetical) hotel with an infinite number of rooms, each one of which is occupied. The hotel gives rise to a paradox: the hotel is full, and yet it has vacancies.

That the hotel is full is obvious. It has an infinite number of rooms, and an infinite of guests; every room is occupied. That the hotel has vacancies is a little more difficult to demonstrate.

Suppose that a new visitor arrives; can he be accommodated? At first it seems that he cannot, but then the hotel clerk has an idea: He moves the guest in Room 1 to Room 2, and the guest in Room 2 to Room 3, and so on. Every guest is moved to the next room along.

For every guest, in every room, there is another room into which they can be moved. This leaves Room 1 vacant for the new visitor. Although the hotel is full, then, the new guest can be accommodated in Room 1.

It is not only one new guest that can be accommodated; in fact, Hilbert’s Hotel has an infinite number of vacancies. By moving every guest to the room the number of which is double the number of their current room, all of the odd numbered rooms can be vacated for new guests. There are, of course, an infinite number of odd numbered rooms, and so an infinite number of new guests can be accommodated.
gillianreynolds

Posts: 1
Joined: Fri Apr 29, 2011 1:05 pm UTC
Location: California

### Re: Hilbert's Hotel...continued

I was discussing this problem with my boyfriend and we came up with this story:

Hilbert's Hotel is hosting the Annual Bus Drivers Convention.

The theme of this year's convention is "seating arrangements and gender". All bus drivers have very strong opinions on how their infinitely many passengers must be organised down the bus. They have a code at the front of the bus telling passengers how they have to sit.

One bus driver's code says "fmfmfmfmfm..." meaning that every odd seat must be occupied by a female, and every even seat must be occupied by a male. Another code says "mmmmmmmm..." meaning that all passengers must be male. Other codes included "fffmmmmm...", "mmffmmf...", "mmfmfmfffff..." and any other code you can think of.

To ensure a wide spread of opinion, the convention has decide that for every possible seating code, they will invite exactly one bus driver who uses that code. In other words, for any (countably) infinite sequence of f and m, there exists a bus driver who endorses that as their preferred seating code.

Each bus driver turned up at the hotel with a bus full of passengers, each seated according to the appropriate code. The passengers don't need rooms at the hotel, they sleep in their seats.

Suppose every bus driver gets a room in the hotel.

One of the bus drivers, named Bob, was not invited to the convention because he's a bigot. Bob has the bizarre hobby of enforcing arranged, heterosexual marriages between his passengers and passengers of other buses. He came up with a plan for a new seating code. Noone changed buses while the following was going on.

Bob wed one of his passengers to the first passenger of the bus driver in the first room of the hotel. The confused and newly married passenger sat in the front seat of Bob's bus. Their spouse remained in their original bus.

Another passenger married the second passenger of the bus driver in the second room, and then sat down in the second seat of Bob's bus. Again Bob's passenger's spouse remained in the bus whose driver was in the second room.

A third passenger married the third passenger of the bus driver in the third room, and then sat down in the third seat of Bob's bus.

This went on until all of Bob's passengers were married and seated. Then Bob wrote down his new code to reflect the way his passengers were seated.

Bob walked right up to Hilbert and said
"I have a seating code that noone else at this convention uses. I demand to attend this convention."
"Impossible! I made sure that every possible code has a representative bus driver in one of our rooms!" Hilbert replied.

"My code is different from the bus whose driver is in the first room, because my first passenger is married to his first passenger, so they are opposite genders. For every n, my code is different to the bus driver in the n'th room, because my n'th passenger is married to that driver's n'th passenger, so they are different genders! My code is proven to be unique!"

Hilbert frowned for a moment and said, "Piss off, we're full".

Posts: 39
Joined: Sat Mar 21, 2009 3:45 am UTC
Location: Perth, Western Australia

### Re: Hilbert's Hotel...continued

I approve of this story.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

skeptical scientist
closed-minded spiritualist

Posts: 6135
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Hilbert's Hotel...continued

The problem with this story, and the reason Bob is able to construct an unused code, is that while the Hotel has countably infinitely many rooms, the infinite of bus drivers is uncountable. It is not possible for every bus driver to have a room in the hotel no matter how you try to map codes to rooms.
douglasm

Posts: 499
Joined: Mon Apr 21, 2008 4:53 am UTC

### Re: Hilbert's Hotel...continued

douglasm wrote:The problem with this story, and the reason Bob is able to construct an unused code, is that while the Hotel has countably infinitely many rooms, the infinite of bus drivers is uncountable. It is not possible for every bus driver to have a room in the hotel no matter how you try to map codes to rooms.

I think that's a feature of the story, not a bug.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5386
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Hilbert's Hotel...continued

Thats an awesome way to explain diagonalization
Ankit1010

Posts: 135
Joined: Fri Feb 11, 2011 11:32 am UTC

### Re: Hilbert's Hotel...continued

Earlier we at the Fake News Network reported on what appeared to be the largest missing persons case in history, here with the latest on this story is FNN's Nota Pérsonne. Take it away Nota.

"As authorities release more details, what at first looked to be the work of a criminal mastermind is appearing more and more to be a case of gross incompetence at the grandest scale. The annual Cardinality Conference was located at the Hilbert Hilton in downtown Continuua this year, when infinitely many tourists in town for the conference vanished without a trace. We now know this is due solely to the terrible room booking strategies employed by the Hilbert Hilton. Before the conference had started, the Hilbert Hilton had already rented out every room to tourists wanting to see the largest event this side of Beth three, but then the busses started arriving and the hotel had to scramble to find rooms for the actual attendees. Not knowing how many busses to expect, the hotel staff chose a simple relocating strategy, simply moving everyone from room N to room 2N and using a standard zeno-accelerated hallway to complete the shuffling in finite time. Unfortunately for practically everyone involved in the event, there were busses comming from ω different cities, and everyone staying at the hotel or siting in a finite seat on a finite numbered bus ended up vanishing into the aether as they were shuffled further and further down the corridor. The hotel is now completely deserted save for the staff and Georg Cantor, who arrived here early and was staying in room zero before this tragic event."
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

WarDaft

Posts: 1553
Joined: Thu Jul 30, 2009 3:16 pm UTC