# Hilbert Hotel: what if countably many buses each with countably many guests arrived?

Situation: There's a hotel owner David Hilbert who owns a hotel with countably many (infinity that can be mapped by natural number surjectively) rooms, and there are countable guests who lived inside starting from room NO:1 and so on.

Now if a guest arrived...I guess we all know what to do--ask everyone to move over to the next door and spare Room NO:1 for the guest.

Now if a bus of countably new guests arrived...we can ask the residents to move to rooms with room number double of their current room number so as to save all the odd-numbered room for the new guests.

Question: But now what if countably many buses each with countably many guests arrived? What can we do to find new rooms for the new guests?

I know that the union of countably many countable sets is countable, and so far I am thinking about something to do with prime number factorization raise to the power of the number of their buses...but then how do I ask the occupants to move...?

Any thoughts or better room-assigning scheme?

-
Not everything about Hilbert has to do with Hilbert spaces. – Asaf Karagila Jan 25 '13 at 0:25
Some none technical thoughts: In reality, I think everyone should start moving to the next room until the new guests are all housed since finding a perfect plan or not they will have to travel. A perfect plan ends up being just as good as the crudest plan. – Sean Jan 25 '13 at 0:47
it makes no difference whether countably many occupants come in countably many buses, or just one bus. the number of buses is irrelevant to the problem. – wim Jan 25 '13 at 1:49
So there is no "bound for the order" for countability? Is it possible to create a mapping f: N->N^3? Something like countable ships holding countable buses with countable tourists arrived at the harbor near Hilbert's Hotel... – Sean Jan 25 '13 at 1:56
btw, I knew that the power set of a countable set is uncountable, so I think there is a boundary somewhere – Sean Jan 25 '13 at 2:20

Move all your guests from the $n$-th room to the $2^n$-th room.

The guests from the $k$-th bus will be placed into the powers of the $k+1$-th prime number. This ensures that all the guests are well-placed, and whatnot.

Alternatively, fix some bijection between $\mathbb N$ and $\mathbb N^2$, and send the guests to the rooms whose numbers are mapped to $(0,n)$ and send the guests from the $k$-th bus to the rooms whose numbers are mapped to $(k,n)$.

-
This is exactly what I had in mind, but I was not sure about the part for moving the guests. Thank you! – Sean Jan 25 '13 at 2:05
btw, did you mean "associate the n-th guest from the k-th bus to the number found by raising the n-th prime number to the (k+1)-th power"? The wording upstairs is a little bit confusing. – Sean Jan 25 '13 at 3:01
Sean, since we essentially inject the square into the line this is symmetric. You can send the $n$-th guest from the $k$-th bus to $p_{k+1}^n$; or to $p_{n+1}^k$ (where $p_i$ is the $i$-th prime number, of course). – Asaf Karagila Jan 25 '13 at 9:54

Since academic salaries are not generous, Hilbert likes his hotel to have full occupancy.

Assume the hotel rooms are numbered $1$, $2$, $3$, and so on.

Move the guest currently occupying room $k$ to room $2k-1$.

The $k$-th person in bus $1$ goes to room $2^1(2k-1)$.

The $k$-th person in bus $2$ goes to room $2^2(2k-1)$.

In general, the $k$-th person in bus $j$ goes to room $2^j(2k-1)$.

We have full occupancy again.

-
I gave that pairing function in one of the homework sheets during this fall semester, only that I made a mistake in the definition and it ended up not being a pairing function at all. Luckily one of the sharper students noticed that and emailed me about the mistake sufficiently long to allow this to be corrected! – Asaf Karagila Jan 25 '13 at 0:37
When I see your answer I couldn't resist myself but to graph it. It is beautiful seeing the guests crawling on a Cartesian coordinate system and table =) – Sean Jan 25 '13 at 1:09

You can have the occupants move in the same way (double their room number), then ask the new guests to take a room based on a diagonalization argument: each bus has a row in an infinite array, so the person in (1,1) takes the first open room, then (1,2), then (2,1), and so on.

-