The Infinite Hotel Paradox - Jeff Dekofsky

Scientific Concepts, Discoveries, and Nature/Numerical Phenomena Presented

Hilbert’s Infinite Hotel Paradox (countable infinity logistics)

An imaginary hotel has infinitely many rooms and is initially fully occupied.

• Single new guest

  • Shift every guest from room n → n+1.
  • This frees room 1 for the new guest.

• Finite number of new guests (e.g., 40)

  • Shift every guest from n → n+40.
  • This frees rooms 1 through 40 for the arriving guests.

• An infinite bus with countably infinitely many passengers

  • Since passengers can be indexed by natural numbers, they can be reassigned systematically.
  • A rearrangement strategy uses n → 2n:
    • Even-numbered rooms become occupied by incoming passengers.
    • Odd-numbered rooms are freed and taken by the waiting bus passengers.

Countable vs. higher (uncountable) infinities

The text emphasizes that the hotel works because it relies only on countable infinity, specifically aleph-zero (Cantor’s size of the natural numbers).

It claims that if the hotel required uncountably infinite resources (for example, the real numbers), then these rearrangements would fail—because there is no simple countable indexing scheme that can enumerate all real numbers.

Prime numbers (Euclid’s theorem) for a no-overlap room assignment

Using the idea attributed to Euclid that there are infinitely many primes, the scheme assigns passengers to rooms via prime-power factorizations.

• Existing hotel guest in room n is sent to 2ⁿ.
• Passengers on:
  • First bus go to rooms of the form 3ᵏ, where k is their seat number.
  • Next bus uses 5ᵏ.
  • Then 7ᵏ, 11ᵏ, etc., for subsequent buses.

Non-overlapping guarantee

• The guarantee comes from unique prime factorization: every natural number has a unique representation of the form 2ᵃ · 3ᵇ · 5ᶜ · ….

• Therefore, assignments like 2ᵃ, 3ᵇ, 5ᶜ, … cannot overlap—no room number is assigned by two different buses.

Note: many room numbers remain unused (e.g., 6) because not every integer is a pure prime power.

---

Methodology / Room-Assignment Scheme (as described)

Single new guest (finite extension)

• Shift each occupant: room n → room (n+1)
• Frees: room 1

40 new guests

• Shift each occupant: room n → room (n+40)
• Frees: rooms 1–40

Infinitely many buses, each with countably infinitely many passengers

• Let the bus index determine the prime base.
• Let the seat/passenger index determine the exponent.
• Steps:
  • Send current guest in room n → 2ⁿ
  • Bus #1 (prime base 3): passenger in seat k → 3ᵏ
  • Bus #2 (prime base 5): passenger in seat k → 5ᵏ
  • Continue for primes 7, 11, 13, 17, …

The claim is that no two passengers land in the same room because prime-power assignments are unique.

---

Researchers or Sources Featured

• David Hilbert
• Georg Cantor
• Euclid