Hilbert's Hotel: Accommodating Infinite Guests

Worked Solution

How to Think About It: This is Hilbert's Hotel, the classic illustration of how infinite sets behave differently from finite ones. The key insight is that "infinity plus something" can still equal infinity -- but you need a concrete procedure (a bijection) to show it. In a finite hotel, full means full. In an infinite hotel, full just means you need a cleverer room assignment. The interviewer wants to see that you understand the difference between finite and infinite cardinality, and that you can construct explicit mappings.

Key Insight: A countably infinite set can be put in one-to-one correspondence with a proper subset of itself. That is the defining feature that makes all three parts work. Each part escalates the challenge: finite union, countable union, and then a countable union of countable sets.

The Method:

*Part 1 -- One new guest:*

Ask every current guest in room $i$ to move to room $i + 1$. The guest in room 1 goes to room 2, room 2 goes to room 3, and so on. Room 1 is now empty -- give it to the new guest.

This works because the map $i \mapsto i + 1$ is a bijection from $\mathbb{N}$ to $\mathbb{N} \setminus \{1\}$. More generally, if $k$ new guests arrive (any finite number), shift everyone from room $i$ to room $i + k$, freeing up rooms $1$ through $k$.

*Part 2 -- Infinitely many new guests:*

Ask every current guest in room $i$ to move to room $2i$. Room 1 goes to room 2, room 2 goes to room 4, room 3 goes to room 6, and so on. This vacates all the odd-numbered rooms: $1, 3, 5, 7, \ldots$ Now assign the $n$-th new guest to room $2n - 1$.

Why does this work? The even numbers $\{2, 4, 6, \ldots\}$ and odd numbers $\{1, 3, 5, \ldots\}$ each form a countably infinite set, and together they cover all of $\mathbb{N}$. You have split one copy of $\mathbb{N}$ into two copies -- each big enough to hold a countably infinite collection.

*Part 3 -- Infinitely many buses, each with infinitely many passengers:*

Label the buses $1, 2, 3, \ldots$ and within each bus, label passengers $1, 2, 3, \ldots$ So every new arrival is identified by a pair $(b, p)$ where $b$ is the bus number and $p$ is the passenger number within that bus. Including the original hotel guests (think of them as bus 0), you need to map the set $\{0, 1, 2, \ldots\} \times \{1, 2, 3, \ldots\}$ into $\mathbb{N}$.

One clean way: use the fact that $\mathbb{N} \times \mathbb{N}$ is countable. Assign each pair $(b, p)$ to room $2^{b} \cdot (2p - 1)$. This maps every (bus, passenger) pair to a unique positive integer because every positive integer has a unique factorization into a power of 2 times an odd number.

Alternatively, use the diagonal (Cantor pairing) enumeration: list all pairs $(b, p)$ along successive diagonals $b + p = 2, 3, 4, \ldots$ and assign rooms in that order.

Practical Considerations: The real point here is not hotel management -- it is understanding cardinality. The shift from Part 2 to Part 3 is where most people stumble. Part 2 feels like you "used up" the trick of splitting $\mathbb{N}$ in two, so how can you split it infinitely many times? The answer is that a countable union of countable sets is still countable. This is a foundational result in set theory and comes up any time you need to argue that some seemingly huge collection of objects is actually enumerable.

Answer: In all three cases, the guests can be accommodated because the set of rooms $\mathbb{N}$ is countably infinite and can be placed in bijection with $\mathbb{N} + k$ (Part 1), $\mathbb{N} \cup \mathbb{N}$ (Part 2), and $\mathbb{N} \times \mathbb{N}$ (Part 3). The explicit mappings are: shift by $k$ for Part 1, send $i \mapsto 2i$ to free odd rooms for Part 2, and use a pairing function (e.g., $2^{b}(2p-1)$) for Part 3.