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
