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.

By a similar procedure, any finite number of new arrivals may be accommodated.

If an infinite number of strangers arrive, they may still be accommodated. The procedure is similar to the finite case, except each current guest will be asked to move to the room with twice the current room number.

All odd-numbered rooms will then become vacant, so the first new guest may move into the first odd-numbered room (1), the second into the second odd-numbered room (3), and so on.