3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Where did you get this problem from? Are you asking for the answer (which you appear to know, at least for part 2) or are you asking for an explanation of an answer you've found? If so, we need to know exactly what form of the answer you want explained. Knowing exactly where you found the problem would be helpful to know what constraints it used. $\endgroup$
    – bobble
    Jul 9 at 16:19
  • 6
    $\begingroup$ This is the well-known Hilbert paradox $\endgroup$
    – melfnt
    Jul 9 at 16:33
  • $\begingroup$ Given that you said how should I exactly approach this I think u should watch this video by Ted-ED. They do a good job explaining it in simple terms. $\endgroup$
    – Varun W.
    Jul 9 at 19:26
  • 1
    $\begingroup$ The issue with your suggestion for question 2 is that the guests already present don't ever get to sleep, and you don't ever finish deciding anyone's room number. If I had room #5, what will my new room number be when you're done assigning everyone new rooms? The doubling method makes the earlier guests move just once, creating an infinite number of available rooms for the infinite newcomers. $\endgroup$
    – aschepler
    Jul 10 at 3:39
  • 2
    $\begingroup$ This is known as the Hilbert Hotel $\endgroup$ Jul 10 at 15:11

2 Answers 2

3
$\begingroup$

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.
- …

$\endgroup$
1
$\begingroup$

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)

$\endgroup$

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.