9
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\begingroup$ Not everything about Hilbert has to do with Hilbert spaces. $\endgroup$
    – Asaf Karagila ♦
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 at 2:20

3 Answers 3

Reset to default
15
$\begingroup$

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.

$\endgroup$
2
  • $\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 ♦
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 at 1:09
11
$\begingroup$

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

$\endgroup$
3
  • $\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
    Commented Jan 25, 2013 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
    Commented Jan 25, 2013 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 ♦
    Commented Jan 25, 2013 at 9:54
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .