Skip to content

Bulbs left on after 100 rounds of toggling

Question

A room has 100100 bulbs, all off, numbered 11 to 100100. Person jj (for j=1,…,100j=1,\dots,100) walks in and toggles every bulb whose number is a multiple of jj. After all 100100 people have passed, how many bulbs are lit?

Short answer

10. Bulb ii is toggled once per divisor of ii, so it ends on exactly when ii has an odd number of divisors. Divisors pair up as d↔i/dd\leftrightarrow i/d except when ii is a perfect square, and there are 1010 squares up to 100100.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution