Hilbert's paradox of the Grand Hotel

related topics
{math, number, function}
{build, building, house}
{theory, work, human}
{day, year, event}
{church, century, christian}

Hilbert's paradox of the Grand Hotel is a mathematical veridical paradox (a true result that is strongly counter-intuitive) about infinite sets presented by German mathematician David Hilbert (1862–1943).

Contents

The Paradox of the Grand Hotel

Consider a hypothetical hotel with countably infinitely many rooms, all of which are occupied – that is to say every room contains a guest. 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.

Finitely many new guests

Suppose a new guest arrives and wishes to be accommodated in the hotel. Because the hotel has infinitely many rooms, we can move the guest occupying room 1 to room 2, the guest occupying room 2 to room 3 and so on, and fit the newcomer into room 1. By repeating this procedure, it is possible to make room for any finite number of new guests.

Infinitely many 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 room n to room 2n, and all the odd-numbered rooms will be free for the new guests.

Infinitely many coaches with infinitely many guests each

It is even possible to accommodate countably infinitely many coach-loads of countably infinite passengers each. The possibility of doing so depends on the seats in the coaches being already numbered (alternatively, the hotel manager must have the axiom of choice at his or her disposal). First empty the odd numbered rooms as above, then put the first coach's load in rooms 3n for n = 1, 2, 3, ..., the second coach's load in rooms 5n for n = 1, 2, ... and so on; for coach number i we use the rooms pn where p is the (i + 1)-st prime number. You can also solve the problem by looking at the license plate numbers on the coaches and the seat numbers for the passengers (if the seats are not numbered, number them). Regard the hotel as coach #0, and the initial room numbers as the seat numbers on this coach. Interleave the digits of the coach numbers and the seat numbers to get the room numbers for the guests. The hotel (coach #0) guest in seat (original room) number 1729 moves to room 01070209 (i.e, room 1,070,209.) The passenger on seat 4935 of coach 198 goes to room 4199385 of the hotel.

Full article ▸

related documents
Regular graph
Row and column spaces
Inner automorphism
Linear function
Identity matrix
Connectedness
Additive function
Elias gamma coding
Random sequence
Inequation
Parse tree
Specification language
Inverse functions and differentiation
Unitary matrix
Unit interval
Euler's identity
Sum rule in differentiation
Column vector
Abelian category
Brun's constant
Elias delta coding
Double precision
Disjunctive normal form
Bookmarklet
Complete category
Lagged Fibonacci generator
Inverse transform sampling
Hamiltonian path problem
Urysohn's lemma
Klein four-group