Home > Riddles > The switches and the million light bulbs

The switches and the million light bulbs

Numerical territoryLevel 5 · Expert · ●●●●●

There are a million light bulbs in a row, all initially turned off. There are a million people.

Person 1 activates all switches (1, 2, 3, ...). Person 2 activates every second switch (2, 4, 6, ...).

Person 3 every third switch (3, 6, 9, ...). So on.

How many light bulbs remain lit at the end and why?

Hints

Show hints
  1. Light bulb n is activated by the people whose numbers divide n.
  2. Final count in $1,\dots,10^6$.
  3. Conclusion: the $1,4,9,16,\dots,1\,000\,000$ bulbs remain on, in total $\boxed{1000}$.

Solution

Show full solution

Answer: They stay on exactly

$$ 1000 $$

bulbs: those with a perfect square index.
1) Mathematical model
The $n$ light bulb is activated by the people whose numbers divide $n$.
Number of bulb actuations $n$:

$$ \tau(n)\quad (\text{number of positive divisors of }n). $$

Since it starts off and each operation inverts the state, it remains on if and only if $\tau(n)$ is odd.
2) When is $\tau(n)$ odd?
Dividers usually come in pairs:

$$ (d,\,n/d). $$

There is a divisor "without a partner" only when:

$$ d=n/d\iff d^2=n, $$

that is, when $n$ is a perfect square.
Therefore:

  • if $n$ is not square, $\tau(n)$ is even;
  • if $n=k^2$, $\tau(n)$ is odd.

3) Final count in $1,\dots,10^6$
The perfect squares in that range are:

$$ 1^2,2^2,\dots,1000^2, $$

because

$$ 1000^2=1\,000\,000. $$

There are exactly 1000 of them.
Conclusion: the light bulbs remain on

$$ 1,4,9,16,\dots,1\,000\,000, $$

in total

$$ \boxed{1000}. $$


Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: Sum and product (two mathematicians) · Next: The three prisoners and the red hats →