144 Chapter 13
Hilbert’s bus
The following week, a considerably larger crowd arrives: Hilbert’s bus pulls up. The bus
has infinitely many seats, numbered like the natural numbers, so there is seat 0, seat 1, seat
2, and so on, and in every seat there is a new guest wanting to check into the hotel. Can the
manager accommodate them?
0
1 2
3
4 5 6
7
8
9
10
11 12
13
14 15 16
17
18
19
20
21 22
23
24 25 26
HILBERT BUS COMPANY
Well, it makes no sense to ask the guests to move up infinitely many rooms, since every
individual room has a finite room number, and so he cannot simply move everyone up as
before. But can he somehow rearrange the current guests so as to make room for the bus
passengers? Please try to figure out a method on your own before reading further!
Interlude. . .
Did you find a solution? The answer is yes, the guests can be accommodated. The
manager simply directs first that the guest currently in room n should move to room 2n,
which frees up all the odd-numbered rooms. And then he directs the passenger in seat s to
take room 2s + 1, which is certainly an odd number, and people in different seats will get
different odd-numbered rooms.
Room n → Room 2n
Seat s → Room 2s + 1
Thus, everyone is accommodated with a room of their own, the previous guests in even-
numbered rooms and the bus passengers in odd-numbered rooms.
Hilbert’s train
Now, Hilbert’s train arrives.
0
HILBERT
0
1
2
3
4
5
6
7
8
9
1
HILBERT
0
1
2
3
4
5
6
7
8
9
2
HILBERT
0
1
2
3
4
5
6
7
8
9
3
HILBERT
0
1
2
3
4
5
6
7
8
9
The train has infinitely many train cars, each with infinitely many seats, and every seat
is occupied. The passengers are each identified by two pieces of information: their car
number c and their seat number s, and every passenger is eager to check into the hotel.
Can the manager accommodate them all?
Interlude. . .