AI summary by TwinMind
The Light Switch Problem - Numberphile
Numberphile
18m 31s
Problem Setup
- 100 light switches, all initially off
- Person 1: turns all switches on
- Person 2: turns every 2nd switch off
- Person 3: toggles every 3rd switch (on→off, off→on)
- Pattern continues through 100 people
- Person n toggles every nth switch
- Question: which switches remain on after all 100 people?
Initial Analysis & Pattern Recognition
- Switches beyond 50th only get toggled once (by their corresponding person number)
- After 4th person, first 4 switches won't change again
- Early pattern observation shows switches 1 and 4 remain on after first few people
- Pattern becomes increasingly complex and difficult to predict manually
Factor-Based Analysis
- Key insight: switch n gets toggled by person k if k is a factor of n
- Prime numbers initially suspected as important
- Prime number 7 has factors: 1, 7 (only 2 factors)
- Gets toggled twice: on by person 1, off by person 7
- All primes end up off (toggled even number of times)
- Number 6 has factors: 1, 2, 3, 6 (4 factors)
- Toggled 4 times: on→off→on→off = off
- General rule: even number of factors → switch ends up off
Factors Come in Pairs Principle
- Most factors come in pairs (e.g., 1×24, 2×12, 3×8, 4×6)
- Exception: when factor pairs itself (perfect squares)
- Number 4: factors are 1, 2, 4 (3 factors total)
- 2×2 creates duplication, reducing pair count
- Number 9: factors are 1, 3, 9 (3 factors total)
- 3×3 creates duplication
Square Numbers Discovery
- Only perfect squares have odd number of factors
- Verified experimentally: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
- These are the switches that remain on
- 10 total switches remain on (perfect squares from 1-100)
Mathematical Proof Using Prime Factorization
- Any number n can be written as: n = p₁^c₁ × p₂^c₂ × ... × pₖ^cₖ
- Number of factors = (c₁+1) × (c₂+1) × ... × (cₖ+1)
- For square numbers: all prime powers cᵢ are even
- Adding 1 to each even power makes all terms odd
- Product of odd numbers is odd → odd number of factors
- For non-squares: at least one cᵢ is odd
- Adding 1 makes at least one term even
- Product with even number is even → even number of factors
Extended Applications
- Highly composite numbers: numbers with more factors than any smaller number
- Number 60: first to have 12 factors in range 1-100
- Number 180: most factors in range 1-200
- Connection to practical divisions: 60 (time), 360 (angles)
- Tau function τ(n): counts number of divisors of n
- Listed as sequence A000005 in Online Encyclopedia of Integer Sequences
