The 100 lockers problem

Question

There are 100 lockers in a row, all initially closed, and 100 students. Student 1 walks by and toggles every locker (opens them all). Student 2 toggles every 2nd locker (2, 4, 6, …), closing them. Student 3 toggles every 3rd locker, and so on, until student 100 toggles only locker 100. "Toggle" means open a closed locker or close an open one. After all 100 students have passed, which lockers are open?

Accepted Answer

The open lockers are exactly the perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ten lockers. Why. Locker n gets toggled by student k precisely when k divides n. So the number of times locker n is toggled equals the number of divisors of n. A locker starts closed, so it ends open if and only if it is toggled an odd number of times, i.e. if and only if n has an odd number of divisors. Which numbers have an odd number of divisors? Divisors normally come in pairs: if d divides n, so does n/d, and these two are distinct. Pairing them up gives an even count, unless a divisor is paired with …

The 100 lockers problem

Your answer

More Brainteasers questions