Light-Bulb Switching Problems

This puzzle looks like it needs simulation — 100 bulbs, 100 passes, track every flip — but the toggle count for each bulb reduces to a single number-theoretic fact once you stop thinking about passes and start thinking about divisors.

The puzzle

100 light bulbs, numbered 1 to 100, all start off. There are 100 people. Person $k$ walks along the row and toggles the switch on every bulb whose number is a multiple of $k$ (so person 1 toggles every bulb, person 2 toggles every even-numbered bulb, and so on up to person 100, who toggles only bulb 100). After all 100 people have gone, which bulbs are on?

Reframe the question. Bulb $n$ starts off, and its final state depends only on how many times it gets toggled — an odd number of toggles leaves it on, an even number leaves it off (it started off, and each toggle flips the state). Person $k$ toggles bulb $n$ exactly when $k$ divides $n$. So the number of times bulb $n$ gets toggled equals the number of positive divisors of $n$.

When is the divisor count odd? Divisors of $n$ normally pair up: if $d$ divides $n$, so does $n/d$, and these are two different numbers ($d \ne n/d$) unless $d = n/d$, i.e. $d = \sqrt n$. So divisors come in pairs except when $n$ is a perfect square, in which case $\sqrt n$ pairs with itself and contributes only one divisor to the count instead of two.

The answer. Bulb $n$ ends up on exactly when $n$ has an odd number of divisors, which happens exactly when $n$ is a perfect square. Among 1 to 100, that's $1, 4, 9, 16, \dots, 100$ — the 10 perfect squares end up lit, and the other 90 bulbs are off.

The reframing habit — trading a simulation for a closed-form count over divisors — is the same move behind sieve-based algorithms (like the Sieve of Eratosthenes) that avoid checking every number against every other number individually.