Problem 31.12 Easy Free

100 Lockers and Toggled Lights

A room has 100100 light bulbs, numbered 11 to 100100, each starting off with its own switch. A sequence of 100100 people enters; the kk-th person flips the switch of every bulb whose number is a multiple of kk. After all 100100 people have passed through, how many bulbs are on?

Work it out, then compare with the answer.

SolutionShow the worked solution

Bulb nn is flipped by person kk exactly when k∣nk\mid n. Every divisor of nn lies between 11 and 100100, so bulb nn is flipped once for each divisor of nn, that is, d(n)d(n) times in total. It starts off, so it ends on if and only if d(n)d(n) is odd.

Pair each divisor kk of nn with n/kn/k. This is an involution on the set of divisors. Its only fixed point would be a divisor with k=n/kk=n/k, that is, k2=nk^2=n. The divisors therefore split into pairs {k,n/k}\{k,n/k\} with k≠n/kk\ne n/k, plus the single divisor n\sqrt n when nn is a perfect square. Hence d(n)d(n) is odd exactly when nn is a perfect square.

The perfect squares in {1,…,100}\{1,\dots,100\} are 12,22,…,1021^2,2^2,\dots,10^2. There are ten of them.

10\boxed{10}

Generalisation. With NN bulbs and NN people, exactly ⌊N⌋\lfloor\sqrt N\rfloor bulbs are on.