allocation of infinity

Question

Suppose you have a hotel which has one floor with infinite number of rooms in a row and all of them are occupied.

1. A new customer wants to check in, how will you accommodate her?
2. What if infinite number of people want to check in, how will you accommodate them?
3. Suppose an infinite number of buses arrive at the hotel, each having an infinite number of people, how will you accommodate them?

My approach: part 1 is cool since you can ask the kth person to move to the k+1th room.

Part 2 is where I am confused. I feel that we should just allow people to move to the next room as the customers come in one by one, probably infinitely, but the answer says to ask kth person to move to room 2k, which is weird for me.

Part 3, I know NxN has a mapping to N but what is it, and how should I exactly approach this?

Answer 1

For 2:

If you make a list of the first few occupied rooms: “1, 2, 3, 4, 5,…”, then double all the numbers, what does the list look like?
What do the missing numbers look like?
You can then easily find an obvious infinite set of empty rooms.

For 3 (make sure you understand part 2 first):

Use the same method to provide an infinite number of vacant rooms.
What happens if you then:

• Assign the first person from the first bus to the first room.

- Assign the second person from the first bus to the second room, and the first person from the second bus to the second room.
- Assign the third person from the first bus, the second person from the second bus, and the first person from the third bus to the next three rooms.
- Assign the next person from the first bus, the next person from the second bus, the next person from the third bus, and the first person from the fourth bus to the next four rooms.
- Assign the next five people from the first five buses to the next five rooms.
- …
- Assign the next N people from the first N buses to the next N rooms.
- …

Answer 2

First of all:

This is known as Hilbert's Paradox, and is a great tool to show how "allocating infinities" can work.

For one guest:

Put the guest in the first available room by asking all of the guests to move to room $n+1$

For an infinite number of guests:

Move the guests already there to room $2n$, giving them an infinite number of even rooms, and for the new arriving guests, an infinite number of odd rooms.

For an infinite number of buses with infinite guests:

Take your guests currently occupying your infinite hotel rooms and ask them (politely) to move to room $2^n$ with $n$ being their old room number.
Then for the first bus, ask people to go into room $3^p$ with $p$ being their seat number in the bus.
For the second bus, ask people to go into room $5^p$.
For any bus $N$, you'll ask the guests inside to go inside the room $P^p$, with $P$ being the $N^{th}$ odd prime number and $p$ being the seat number of the guest in the bus. That way, you'll never run out of space, and will manage to fill in "infinity infinities" of guests inside your hotel.
(This is only one of the methods to fit an infinite number of buses, using powers of primes and their uniqueness)