The 1000 Lightbulbs Puzzle: Why Perfect Squares Are the Key

The 1000 Lightbulbs Puzzle: Can You Solve It?

Those brain cells won’t stretch themselves. Let’s try this one:

You have a row of 1000 numbered lightbulbs.

On the first pass, you turn all of them on.
On the second pass, you toggle every second bulb (even numbers — off).
On the third pass, you toggle every third bulb (on if off, off if on).
On the fourth pass, you toggle every fourth bulb.
…
This process continues for 1000 passes in total, until on the final pass you toggle only bulb #1000.

How many lightbulbs are left on at the end?

The Key Insight: Divisors and the 1000 Lightbulbs Puzzle

Each bulb gets toggled once for every divisor it has. For example, bulb #12 is touched exactly 6 times — by passes 1, 2, 3, 4, 6, and 12.

The critical observation: almost every number has an even number of divisors, because divisors naturally come in pairs. If $d$ divides $n$, then so does $n/d$. That means every bulb with an even divisor count starts off (pass 1 turns it on) and ends up toggled an even number of times total — finishing off.

Why Perfect Squares Are the Exception

There is one exception: numbers whose divisor count is odd. This only happens for perfect squares.

Why? Because in a perfect square, one divisor is paired with itself. Take 16 as an example — its divisors are 1, 2, 4, 8, 16, and 4 is its own pair (4 × 4 = 16). That unpaired divisor makes the total count odd, so the bulb ends up toggled an odd number of times — finishing on.

Solving the Puzzle: Counting Perfect Squares up to 1000

The lightbulbs that remain on correspond exactly to the perfect squares from 1 to 1000.

We need to count how many perfect squares satisfy $n^2 \leq 1000$:

$$1^2, \ 2^2, \ 3^2, \ \ldots, \ 31^2 = 961 \leq 1000$$
$$32^2 = 1024 > 1000$$

That gives us 31 perfect squares.

Answer: 31 lightbulbs remain on.