The 100 Lockers

Question

100 closed lockers line a hallway. Person 1 toggles every locker, person 2 toggles every 2nd locker, person k toggles every k-th, up to person 100. After all 100 passes, which lockers are open, and how many?

Accepted Answer

Locker n is toggled by exactly the persons k that divide n, so its final state depends on the parity of the number of divisors of n. Divisors come in pairs d leftrightarrow fracnd, so the count is even, unless some divisor pairs with itself, i.e. d = fracnd iff n = d^2. Only perfect squares have an odd number of divisors. Open lockers: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, exactly lfloor sqrt100 rfloor = mathbf10. This is a purely structural argument, no simulation, one symmetry observation. When you give it, also volunteer the sanity check: locker 12 has divisors 1,2,3,4,6,12 (6 toggles → closed), locker 16 has 1,2,4,8,16 (5 toggles → open). Checking a small case out loud is exactly the habit these interviews reward.

The 100 Lockers

Problem

Your answer

Hints

More Brainteasers & Logic to train on