The Locker Problem

When I first read the blog post presenting the problem, I immediately concluded that each student changes the state of the lockers that have a number that is a multiple of the student’s number. That didn’t help much. I had to think of it from the lockers’ point of view.

Yeah, that’s not that hard. The locker will be changed by the students whose numbers are a factor of the locker’s number. Okay. If the lockers start open, lockers with an even number of factors would stay open and lockers with an odd number of factors would be closed. Easy. Final answer. Done.

Then I started thinking if there was a better answer for that. But how do I know which numbers have an even or odd number of factors? And I thought I’d have to brute force my way through it. No, it can’t be! That’s not how we do things. So I started thinking about factors, and as it usually goes I thought that prime numbers have only 1 and themselves as factors! That’s it. Prime numbers have an even number of factors, everything else must have an odd number, right? Then just to check I thought of 6. And it turns out that 6 has 1, 2, 3, and 6 as factors. Four factors. Four is even… Wait. Of course! Factors come in pairs. Always! The factors of a number n always come as a×b = n. But then does that mean every single number has an even number of factors and therefore every door is open? Can’t be!

I had to try and brute force the start. Starting with 1 I found that it had only itself as a factor. Wait a second there. 1 is a weird number, so maybe only 1 is closed and everything else is open? Let’s keep checking before we conclude that… Continue brute forcing: 2 has two factors, 3 has two factors, 4 has... Three? Wait! How? What about the factor pairs? 4 is 1×4 and 2×2. OOOH! One of the pairs is a number times itself! So that is a pair, but that number only shows up once in the list of factors. That is the odd factor! The factor that doesn't have a pair other than itself! The square root of the number! It has to be it! Perfect square numbers have an odd number of factors. Also, 1 is a special number in many ways, but also it is a perfect square. Of itself! Brute forced my way to 10 just to check and, as expected, locker 9 was closed!

That’s a beautiful problem. That is a problem that would make me enthusiastically tell the students “that’s why math is the most beautiful thing in the universe!” To which I know most students would just sigh, but such is life…

I built a small interactive visualisation here to help see the first 50 lockers and the first 50 students (we don't need more students because no student after the 50th would touch the first 50 lockers).

Interactive Visualisation