From: veritasium
The Hilbert Hotel is a conceptual hotel featuring an infinite number of rooms, numbered sequentially from one onwards [00:00:01] [00:00:06]. As the manager of this hotel, one might initially assume it can always accommodate any number of guests [00:00:16]. However, there are limits to even the infinity of rooms available [00:00:19].
Accommodating New Guests
A Single New Guest
If the hotel is full with an infinite number of people, and one new guest arrives, they can still be accommodated [00:00:30] [00:00:37]. The solution is to announce to all existing guests to move down one room: the person in room one moves to room two, room two to room three, and so on [00:00:48] [00:00:50]. This frees up room one for the new guest [00:00:58].
A Finite Group of New Guests
Similarly, if a bus with a finite number of people, such as a hundred, arrives, the same principle applies [00:01:01]. All existing guests move down a hundred rooms, vacating the first hundred rooms for the new arrivals [00:01:04].
An Infinitely Long Bus
When an infinitely long bus carrying an infinite number of people arrives, a different strategy is needed [00:01:09]. Existing guests are instructed to move to the room with double their current room number (e.g., room one to room two, room two to room four) [00:01:25]. This frees up all odd-numbered rooms [00:01:37]. Since there are an infinite number of odd numbers, each person from the infinite bus can be assigned a unique odd-numbered room [00:01:41] [00:01:44].
An Infinite Number of Infinite Buses
The hotel can even accommodate an infinite number of infinitely long buses [00:01:57]. This is managed by conceptualizing an infinite spreadsheet [00:02:08]:
- Rows represent the existing hotel guests and each incoming bus (Bus 1, Bus 2, etc.) [00:02:11].
- Columns represent the position of each person (Hotel Room 1, Bus 1 Seat 1, etc.) [00:02:19].
Each person gets a unique identifier based on their vehicle and position [00:02:32]. To assign rooms, a line is drawn that zigzags across the spreadsheet, touching every unique ID exactly once [00:02:41]. This effectively transforms an infinite-by-infinite grid into a single infinite line, allowing each person to be matched with a unique room in the hotel [00:02:51] [00:02:57].
The Limit: Uncountably Infinite Guests
Despite the hotel’s ability to accommodate vast numbers of guests, there is a limit. This limit is demonstrated by a “big bus” where guests are identified by infinitely long names consisting only of the letters ‘A’ and ‘B’ [00:03:12] [00:03:20]. Every possible infinite sequence of these two letters is represented by a person on the bus [00:03:40].
The challenge arises when trying to assign these guests to rooms using a spreadsheet [00:04:08]. Even if an infinite list of room assignments is created, it’s always possible to construct the name of a person who is not on that list [00:04:25]:
- Take the first letter of the name in Room 1 and flip it (A to B, or B to A) [00:04:33].
- Take the second letter of the name in Room 2 and flip it [00:04:39].
- Continue this process down the diagonal of the list, flipping the nth letter of the nth name [00:04:43].
The resulting newly constructed name will differ from every name on the list by at least one character (the diagonal letter), proving it’s not accounted for [00:04:46] [00:04:58].
Countably vs. Uncountably Infinite
The Hilbert Hotel’s rooms represent a countably infinite set, meaning there are as many rooms as there are positive integers (1, 2, 3…) [00:05:06] [00:05:10]. In contrast, the number of people on the “big bus” is uncountably infinite [00:05:16]. If one attempts to match each of these people with an integer (a room number), there will always be people left over [00:05:22]. This illustrates that some infinities are bigger than others [00:05:27], and represents a limit to the Hilbert Hotel’s capacity [00:05:32].
The discovery of different sized infinities profoundly influenced subsequent scientific inquiry, ultimately leading to the invention of modern computing devices [00:05:41] [00:05:44].