A Hundred Bulbs, 482 Flips, and Ten Survivors

A hundred light bulbs stand in a row, numbered $1$ to $100$, all switched off. A hundred people walk the row in turn. Person $1$ flips every bulb. Person $2$ flips bulbs $2, 4, 6, \dots$. In general person $k$ flips every bulb whose number is a multiple of $k$. After person $100$ has finished, which bulbs are on?

Ten of them: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$. The perfect squares, and nothing else. People asked this for the first time usually expect a scatter with no pattern, or something near half the row, and the actual answer is both sparser and far more structured than either guess. A total of $482$ flips happen, and they cancel almost perfectly.

Count the flips, not the bulbs

Person $k$ touches bulb $n$ exactly when $k$ divides $n$. Nobody else touches it. So the number of times bulb $n$ is flipped is the number of positive divisors of $n$, written $d(n)$. Bulb $64$ is flipped by persons $1, 2, 4, 8, 16, 32, 64$, so $d(64) = 7$.

This is also why stopping at person $100$ loses nothing. Every divisor of a number at most $100$ is itself at most $100$, so no later person would have anything left to do.

The bulb starts off and every touch changes its state, so the state at the end is decided by the parity of the flip count alone. Bulb $n$ is on at the end if and only if $d(n)$ is odd. The problem has now been converted from a process into a question about a number, and the process can be forgotten.

Divisors come in pairs, with one exception

Divisors are not scattered at random through the range. If $d$ divides $n$ then so does $n/d$, and the map $d \mapsto n/d$ sends the divisors of $n$ to themselves and is its own inverse. Applying it twice gets you back where you started, which makes it an involution on a finite set. An involution splits that set into two-element orbits together with its fixed points, so

A fixed point is a divisor with $d = n/d$, that is $d^2 = n$. There is at most one such positive $d$, and it exists exactly when $n$ is a perfect square. Everything else pairs off and contributes an even amount.

Combining the two steps: bulb $n$ ends up on exactly when $n$ is a perfect square. Between $1$ and $100$ the squares are the ten numbers $1^2$ through $10^2$.

The same result through the prime factorisation

The pairing argument is the one to give under time pressure, but it is worth seeing the result fall out of the structure of $d$ as well, because that version generalises where the pairing does not. If $n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ then a divisor is built by choosing each exponent independently, so

A product of integers is odd exactly when every factor is odd, so $d(n)$ is odd exactly when every $e_i + 1$ is odd, which means every $e_i$ is even, which means $n$ is a square. Take $36 = 2^2 \cdot 3^2$: the count is $3 \cdot 3 = 9$, odd, so bulb $36$ is lit. Take $60 = 2^2 \cdot 3 \cdot 5$: the count is $3 \cdot 2 \cdot 2 = 12$, even, so bulb $60$ is dark.

Two arguments that share no step and agree on all hundred bulbs. I trust the answer more for having both.

The half-the-row guess gets worse as the row gets longer

The reflex answer deserves a fair hearing. Roughly $482$ flips are spread over a hundred bulbs, so the average bulb is flipped nearly five times, and a coin flipped nearly five times has no strong preference. If parities behaved like independent coin tosses, half the row would be lit. They do not behave that way at all, and the reason is that the parity is pinned by an algebraic accident rather than accumulated at random.

The number of survivors in a row of $N$ bulbs is the number of squares up to $N$, which is

At $N = 100$ that is $10$, a tenth of the row. At $N = 10^6$ it is a thousand, one bulb in a thousand. The lit fraction is $1/\sqrt{N}$and it goes to zero, so the guess "about half" is not off by a constant. It gets worse the longer the row.

The process needs all hundred people

A tempting economy is to think that the late people, who touch only one or two bulbs each, cannot matter much. They matter completely. Stop after person $50$ and the row leaves $54$ bulbs lit, more than five times the true answer, and the pattern inverts. For any $n$ above $50$ the second largest divisor is at most $n/2 \le 50$, so the only divisor missing from a truncated run is $n$ itself. The flip count becomes $d(n) - 1$, which is odd exactly when $d(n)$ is even, so every non-square above $50$ is left glowing and the three squares $64, 81, 100$ are the ones switched off.

This is the kind of detail I would want a candidate to volunteer. The clean answer depends on the process running long enough that each bulb sees all of its divisors, and the problem is set up so that it just barely does.

Sources and further reading

• The function $d(n)$ and its multiplicativity — Divisor function
• The set that survives — Square number
• Why (3) counts divisors — Fundamental theorem of arithmetic
• The structure behind equation (1) — Involution

The answer was checked by actually switching a hundred bulbs a hundred times, holding a list of booleans and assuming nothing about divisors, and the resulting set matched (2) exactly. On top of that, the flip count was confirmed equal to $d(n)$ for every bulb, the pairing $d \mapsto n/d$ was verified to be an involution with a fixed point exactly at the squares for every $n$ up to $300$, and the theorem above was pushed out to $n = 5000$, well past where a coincidence on a hundred-wide grid could survive. The count in (4) was compared against a direct count of squares for every $N$ up to $2000$.