Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
show 1 more comment

3 Answers

up vote 10 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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