100 bulbs, 100 people. Which stay lit?
The bulb-switching puzzle: 100 bulbs all start off, and person k toggles every k-th bulb. After all 100 passes, which bulbs are on? The answer hides a fact about divisors that most people have never had a reason to notice.
A corridor holds 100 light bulbs, numbered 1 to 100, all switched off. One hundred people walk the corridor in turn.
- Person 1 toggles every bulb (all 100 turn on).
- Person 2 toggles every 2nd bulb (2, 4, 6, ... now go off).
- Person 3 toggles every 3rd bulb (3 goes off, 6 comes back on, and so on).
- In general, person k toggles bulbs k, 2k, 3k, up to 100.
After person 100 has walked the corridor, which bulbs are lit? And how many?
Brute force is available to anyone with a laptop: a hundred passes over a hundred-element boolean array settles it in microseconds. The interview version of the question does not accept that. You must name the lit bulbs, and say why those and no others, without simulating a single pass.
A useful reframing before the hints: forget the sequence of events and pick a single bulb, say bulb 12. Its final state depends only on how many times it gets toggled across all 100 passes. Odd count means on, even count means off. So the entire puzzle collapses into one question about the number 12. What is that question?
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Person k touches bulb n exactly when k divides n evenly. So the number of times bulb n is toggled equals the number of divisors of n. Bulb 12 is toggled by persons 1, 2, 3, 4, 6, and 12: six toggles, so it ends off.
Hint 2 the key move
Divisors arrive in pairs: if d divides n, then n/d divides n too. 12 pairs up as (1,12), (2,6), (3,4). Pairs contribute an even count, and even means off. When can a "pair" fail to be two distinct numbers?
Hint 3 nearly the answer
The pairing d with n/d collapses to a single number exactly when d = n/d, that is, when n is a perfect square. Only those n have an odd divisor count. Now list the perfect squares up to 100.
The solution
Reveal the full solution
The lit bulbs are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. Ten bulbs: the perfect squares.
The argument runs in three short steps. First, bulb n is toggled once for each k that divides n, so its toggle count is d(n), the number of divisors of n. Second, its final state is on exactly when d(n) is odd, since every bulb starts off and each toggle flips it. Third, d(n) is odd exactly when n is a perfect square.
That last step is the heart of the puzzle. Divisors of n pair up naturally: match each divisor d with its partner n/d. For n = 36, the pairs are (1,36), (2,18), (3,12), (4,9), and then (6,6), where the pairing scheme hands you the same number twice. That collapsed pair is the only way an odd divisor count can arise, and it happens precisely when n has an integer square root. Every non-square has all its divisors in clean two-element pairs, hence an even count, hence a dark bulb.
So the corridor performs a number-theory computation by accident: it is a physical sieve that isolates perfect squares.
What this puzzle is really testing
The winning move was changing the unit of analysis. The problem narrates 100 sequential passes, which invites you to simulate time. The solution instead fixes one bulb and asks what the whole process does to it, turning a dynamic story into a static counting question. That per-element shift is the same instinct behind frequency counting, where you stop replaying events and just tally what each element experienced, and it is the lens that makes hash map solutions feel obvious once you see them.
Follow-ups to expect
Three common extensions: which bulbs are toggled exactly twice (the primes, touched only by 1 and themselves); what changes if person k instead toggles bulbs numbered by multiples of k squared; and the general count of lit bulbs for n bulbs, which is the floor of the square root of n. None require new machinery, only the same divisor-pairing argument aimed at a new target. For the counting habit in code form, the seen-so-far pattern is the natural next read.