How An Infinite Hotel Ran Out Of Room

Veritasium

33,371,788 views • 5 years ago 6 min read

Video Summary

The Hilbert Hotel, with its infinite rooms numbered sequentially, presents a challenge when new guests arrive. If all rooms are full, the manager can accommodate a single new guest by having everyone shift to the next room. Similarly, if 100 new guests arrive, everyone shifts 100 rooms down, freeing up the first 100 rooms.

When an infinitely long bus with infinitely many people arrives, the manager has them move to rooms that are double their current room number. This opens up all the odd-numbered rooms, providing enough space for everyone on the bus. The problem escalates with an infinite number of infinite buses. To manage this, an infinite spreadsheet is used, assigning each person a unique identifier based on their bus and seat number. By creating a zigzagging path through this grid, all individuals can be mapped to a single infinite line, and subsequently, to unique hotel rooms.

However, a different challenge arises with a bus carrying people whose names are infinitely long sequences of "A" and "B". Despite the infinite rooms, a new person can always be created who is not on the list of assigned rooms by constructing a name that differs from each assigned name at a specific diagonal position. This demonstrates that the hotel's infinity is "countably infinite," while the bus with infinite name combinations represents a "uncountably infinite" set, revealing that some infinities are larger than others.

Short Highlights

The Hilbert Hotel can accommodate new guests, even when full, by having existing guests shift rooms.
An infinite number of new guests can be accommodated by having existing guests move to rooms with double their current number, freeing up odd-numbered rooms.
An infinite number of infinite buses can be managed by assigning unique identifiers and mapping them to a single infinite line.
A bus with people whose names are infinitely long sequences of "A" and "B" represents an uncountably infinite set.
The hotel's rooms are countably infinite, while the set of all possible infinite sequences of "A" and "B" is uncountably infinite, meaning some infinities are larger than others.

Key Details

The Hilbert Hotel and Finite Additions [0:01]

The Hilbert Hotel has an infinite number of rooms, numbered 1, 2, 3, and so on, forever.
If the hotel is full, and one new person arrives, the manager can accommodate them by asking every guest to move to the next room (e.g., guest in room 1 moves to room 2, guest in room 2 moves to room 3).
This frees up room 1 for the new guest.
If a bus with 100 people arrives, the manager can have everyone move down 100 rooms, freeing up rooms 1 through 100 for the new arrivals.

This illustrates how even a full infinite hotel can accommodate a finite number of new guests through simple room reassignments.

"So the person in room one moves to room two. The one in room two moves to room three, and so on down the line. And now you can put the new guest in room one."

The Hilbert Hotel and Infinite Additions [1:09]

When a bus with an infinite number of people arrives, a different strategy is needed.
The manager instructs each existing guest to move to the room with double their current room number (e.g., room 1 to room 2, room 2 to room 4, room 3 to room 6).
This leaves all the odd-numbered rooms available.
Since there are an infinite number of odd numbers, each person on the infinite bus can be assigned a unique odd-numbered room.

This demonstrates how an infinite hotel can accommodate an infinite number of new guests, as long as the set of new guests is "countably infinite."

"And now all of the odd numbered rooms are available. And you know, there are an infinite number of odd numbers. So you can give each person on the infinite bus, a unique, odd numbered room."

The Hilbert Hotel and Infinite Infinite Additions [2:06]

The challenge becomes even greater when an infinite number of infinite buses arrive.
To manage this, an infinite spreadsheet is used, with rows for each bus and a row at the top for existing guests.
Columns represent hotel room numbers and seats on the buses.
Each person is assigned a unique identifier based on their bus and position.
A zigzagging path across this infinite grid assigns each unique ID exactly once, effectively turning an infinite by infinite grid into a single infinite line.
This allows each person on the line to be matched with a unique room.

This strategy shows how to accommodate an infinite number of infinite sets of guests by creating a mapping to a single linear sequence.

"So you've got hotel room one, hotel room two, hotel room three, et cetera. And then bus one seat one, bus one seat two, bus one seat three and so on."

The Limit of Infinity: Uncountably Infinite Sets [3:12]

A new scenario involves a bus with people identified by infinitely long names composed only of "A" and "B."
Every possible infinite sequence of "A" and "B" is represented on this bus.
The manager attempts to assign rooms by creating a list of names and then constructing a new name that is guaranteed not to be on the list.
This is done by taking the first letter of the first name and flipping it, the second letter of the second name and flipping it, and so on.
The resulting name differs from every name on the list by at least one character at a diagonal position.

This process, known as Cantor's diagonal argument, proves that there are more possible infinite sequences of "A" and "B" than there are positive integers.

"The way you do it is you take the first letter of the first name and flip it from an A to a B. Then take the second letter of the second name and flip it from a B to an A. And you keep doing this all the way down the list."

Countable vs. Uncountable Infinity [5:06]

The rooms in the Hilbert Hotel are "countably infinite," meaning they can be matched one-to-one with the positive integers (1, 2, 3, ...).
The set of people on the bus with infinitely long "A" and "B" names is "uncountably infinite."
It is impossible to match each person on this bus with a unique integer; there will always be people left over.
This highlights that some infinities are genuinely larger than others.

The discovery of different sizes of infinity has profound implications, even leading to the development of modern technology.

"The number of rooms in the Hilbert Hotel is infinite, sure, but it is countably infinite. Meaning there are as many rooms as there are positive integers one to infinity."