AI summary by TwinMind

A Problem with Infinite Hotel Keys - Numberphile

Numberphile

18m 2s

Problem Setup

  • Hilbert's Hotel with infinite rooms and infinite keys
  • All keys mixed up in bucket, need to assign randomly to hooks
  • Question: probability at least one key matches correct room
  • Approach: pull keys randomly, place on hooks sequentially (key 1 → hook 1, key 2 → hook 2, etc.)

Mathematical Framework

  • Define Ai = event that key i is on correct hook i
  • Want P(A1 ∪ A2 ∪ A3 ∪ ...) = probability at least one key correct
  • Use inclusion-exclusion principle for infinite case
  • Start with finite n rooms, then take limit to infinity

Inclusion-Exclusion Principle Development

  • n=2 case: P(A1 ∪ A2) = P(A1) + P(A2) - P(A1 ∩ A2)
    • Venn diagram shows double-counting overlap requires subtraction
  • n=3 case: Add all singles, subtract all pairs, add back triple intersection
    • Pattern: alternating signs due to over/under counting corrections
  • General formula:
    • Include all single events
    • Exclude all double intersections
    • Include all triple intersections
    • Continue with alternating signs: (-1)^(k+1)

Probability Calculations

  • Single event: P(Ai) = 1/n (one correct key out of n total)
  • Double event: P(Ai ∩ Aj) = (1/n) × (1/(n-1)) = 1/(n(n-1))
  • Triple event: P(Ai ∩ Aj ∩ Ak) = 1/(n(n-1)(n-2))
  • k events: 1/(n(n-1)(n-2)...(n-k+1)) = 1/(n!/(n-k)!) = (n-k)!/n!

Counting Terms in Sums

  • Single terms: n terms (straightforward)
  • Pairs: C(n,2) = n(n-1)/2 terms (combinations without replacement)
  • Triples: C(n,3) = n(n-1)(n-2)/6 terms
  • k-tuples: C(n,k) = n!/(k!(n-k)!) terms

Algebraic Simplification

  • Substituting counts and probabilities creates telescoping cancellations
  • First term: n × (1/n) = 1
  • Second term: [n(n-1)/2] × [1/(n(n-1))] = 1/2
  • Third term: [n(n-1)(n-2)/6] × [1/(n(n-1)(n-2))] = 1/6 = 1/3!
  • Pattern: Each term becomes 1/k! where k is number of events

Series Recognition and Euler's Connection

  • Final form: 1 - 1/2! + 1/3! - 1/4! + 1/5! - ...
  • Recognize as related to Euler's exponential series: e^x = Σ(x^k/k!) from k=0 to ∞
  • With x = -1: e^(-1) = 1 + (-1)/1! + (-1)²/2! + (-1)³/3! + ...
  • Series becomes: e^(-1) = 1 - 1/1! + 1/2! - 1/3! + 1/4! - ...

Final Result

  • Probability = 1 - 1/e ≈ 0.632 = 63.2%
  • Interpretation: 63% chance at least one guest gets correct key for their room
  • Complement: 37% chance no keys match (1/e ≈ 0.368)
  • Result independent of hotel size - holds for infinite case

Extensions and Follow-up Questions

  • Brady asks about probability exactly two people get correct keys
  • Demonstrates mathematical curiosity about related probability distributions
  • Opens discussion for derangement problems and exact k matches

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome