Hilbert's hotel

Hilbert's hotel is a popular illustration of some properties of infinite sets like the set of natural numbers (and other countably infinite sets).

The story — which is usually attributed to 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

Introduction

Imagine a hotel with infinitly 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 accomodated: 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 versions of the story it is usually 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 always leave every second available room free when distributing arriving guests.