100 Lockers and Toggled Lights
A room has light bulbs, numbered to , each starting off with its own switch. A sequence of people enters; the -th person flips the switch of every bulb whose number is a multiple of . After all people have passed through, how many bulbs are on?
Work it out, then compare with the answer.
SolutionShow the worked solution
Bulb is flipped by person exactly when . Every divisor of lies between and , so bulb is flipped once for each divisor of , that is, times in total. It starts off, so it ends on if and only if is odd.
Pair each divisor of with . This is an involution on the set of divisors. Its only fixed point would be a divisor with , that is, . The divisors therefore split into pairs with , plus the single divisor when is a perfect square. Hence is odd exactly when is a perfect square.
The perfect squares in are . There are ten of them.
Generalisation. With bulbs and people, exactly bulbs are on.