Hilbert's grand hotel

Hilbert's paradox of the Grand Hotel, or simply Hilbert's Hotel, is a thought experiment which illustrates a counterintuitive property of infinite sets. It is demonstrated that a fully occupied hotel with infinitely many rooms may still accommodate additional guests, even infinitely many of them, and that this process may be repeated infinitely often. The idea was introduced by David Hilbert in a 1924 lecture "Über das Unendliche" reprinted in (Hilbert 2013, p.730) and was popularized through George Gamow's 1947 book One Two Three... Infinity.

Consider a hypothetical hotel with a countably infinite number of rooms, all of which are occupied. One might be tempted to think that the hotel would not be able to accommodate any newly arriving guests, as would be the case with a finite number of rooms, where the pigeonhole principle would apply.

Suppose a new guest arrives and wishes to be accommodated in the hotel. We can (simultaneously) move the guest currently in room 1 to room 2, the guest currently in room 2 to room 3, and so on, moving every guest from his current room n to room n+1. After this, room 1 is empty and the new guest can be moved into that room. By repeating this procedure, it is possible to make room for any finite number of new guests.

It is also possible to accommodate a countably infinite number of new guests: just move the person occupying room 1 to room 2, the guest occupying room 2 to room 4, and, in general, the guest occupying room n to room 2n, and all the odd-numbered rooms (which are countably infinite) will be free for the new guests.

It is possible to accommodate countably infinitely many coachloads of countably infinite passengers each, by several different methods. Most methods depend on the seats in the coaches being already numbered (or use the axiom of countable choice). In general any pairing function can be used to solve this problem. For each of these methods, consider a passenger's seat number on a coach to be ${\displaystyle n}$, and their coach number to be ${\displaystyle c}$, and the numbers ${\displaystyle n}$ and ${\displaystyle c}$ are then fed into the two arguments of the pairing function.

...
Wikipedia