Hilbert's Hotel...continued

[afarnen]

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?

The answer:

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.

The answer:

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?

[douglasm]

Trivial solution:

Spoiler:

Suppose you have a function f(m, n) that maps from NxN to N. For N^x, simply apply it x-1 times. So, for N⁵ you'd have f(f(f(f(a, b), c), d), e).

[afarnen]

What about N^infinity?

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

[6453893]

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.

[douglasm]

What about N^infinity?

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.

[MartianInvader]

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.

[antonfire]

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?

[Goldstein]

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.

[quintopia]

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.

[Goldstein]

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.

[gillianreynolds]

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.

[Madge]

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

[skeptical scientist]

I approve of this story.

[douglasm]

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.

[jestingrabbit]

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.

[Ankit1010]

Thats an awesome way to explain diagonalization

[WarDaft]

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