Hilbert's hotel

Hilbert's hotel is an often used popular illustration of some properties of infinite sets like the set of natural numbers (or any other countably infinite set).

In particular, it shows that infinite subsets of countably infinite sets have as many elements as the set, and that the "sum" of two countable sets is also countable.

The story — which is usually attributed to the German mathematician David Hilbert — appears in a book (One two three ... infinity, 1947) by George Gamow (in Chapter 1, Big Numbers, pp.17-18) with the following footnote:

From the unpublished, and even never written, but widely circulating volume: "The Complete Collection of Hilbert Stories" by R. Courant.

The story

Imagine a hotel with infinitely many rooms, the room numbers being all natural numbers. Assume further that the hotel is fully booked — all rooms are occupied.

Nevertheless, if a new guest arrives he need not be sent away because the manager can provide a room by asking all guests to move: the guest in room 1 into room 2, the guest in room 2 into room 3, the guest in 3 into 4, and so on, i.e., each guest moving from room number n to room number n+1. Thus room number 1 will become free for the new guest.

Imagine now the arrival of a bus with infinitely many tourists. They still can be accommodated: This time the manager asks the guests to move from 1 to 2, from 2 to 4,from 3 to 6, and so on, namely from n to 2n. After this, only the rooms with even numbers are occupied, and the tourists can be put in the rooms with odd numbers.

Curiously, in the many circulating versions of the story it usually is not mentioned that the manager could exclude some (even infinitely many) VIPs from moving and, more interesting, that he could spare all guests the inconvenience of moving by good advance planning: He simply must — when assigning rooms to arriving guests — leave free every second available room.