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?

  • 3
    $\begingroup$ Not everything about Hilbert has to do with Hilbert spaces. $\endgroup$
    – Asaf Karagila
    Jan 25 '13 at 0:25
  • $\begingroup$ 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. $\endgroup$
    – Sean
    Jan 25 '13 at 0:47
  • $\begingroup$ 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. $\endgroup$
    – wim
    Jan 25 '13 at 1:49
  • $\begingroup$ 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... $\endgroup$
    – Sean
    Jan 25 '13 at 1:56
  • $\begingroup$ btw, I knew that the power set of a countable set is uncountable, so I think there is a boundary somewhere $\endgroup$
    – Sean
    Jan 25 '13 at 2:20

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.

  • $\begingroup$ 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! $\endgroup$
    – Asaf Karagila
    Jan 25 '13 at 0:37
  • $\begingroup$ 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 =) $\endgroup$
    – Sean
    Jan 25 '13 at 1:09

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)$.

  • $\begingroup$ This is exactly what I had in mind, but I was not sure about the part for moving the guests. Thank you! $\endgroup$
    – Sean
    Jan 25 '13 at 2:05
  • $\begingroup$ 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. $\endgroup$
    – Sean
    Jan 25 '13 at 3:01
  • $\begingroup$ 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). $\endgroup$
    – Asaf Karagila
    Jan 25 '13 at 9:54

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.