The Locker Problem

Right at the moment of hearing about this problem, I thought, "This sounds easy! I already know what this question is asking about, and I already have ideas brewing." Little did I know, I would be spending a bit more time on this problem than I thought.

The first thing I did when I sat down was to establish the problem. As such, I wrote down the premise and drew a picture of some numbered lockers.

After that, I thought back to my initial brainstorming when the question was introduced: what if I used the fact that each locker is only opened when a student's number is a divisor of the locker's number? This property holds every time; for example, locker 1000 would be opened by the 2nd, 4th, 25th, 500th students, or another one along these lines. Thus I began to explore, as I now had a lead.

The premise here was to create a flow chart for each locker door. I quickly shelved the red text in the image since I wanted a more catch-all flow chart. I noted another truth: if a locker's state changes an even number of times, it doesn't actually change at all, whereas an odd number of times would change the state in the end. For example, closing and opening (2 changes) versus simply closing (1 change). Thus, whether we had an odd or even number of divisors was the key to deciding the locker's state.

So now the goal (note that there's a lot of narrowing in on goals here) is to figure out an easy way to get the number of divisors for a number. 

Fortunately, I remembered a very nice function definition from the number theory course I took last year (okay B.Ed breadth requirements, you win): the tau function to get the number of divisors of a positive integer! All that is needed is to get the n = p1^a1 * ... * pr^ar prime factorization of the number, with 'pi' being a unique prime, and 'ai' being a power.

Upon further inspection of the tau function definition, the conclusion I reached was this: if at least one 'an' were odd, then the number of divisors would be odd, which means the locker would be closed. The first 12 lockers were explored in the picture above, along with 180 since it was a number with two even-powered prime factors and one odd-powered prime factor.

Eventually, I came up with this flow chart to tell if a locker was open or closed:

Of course, we can simplify further based on the red text at the bottom-right corresponding to the first composite case. If every power in the prime factorization is even, then you could rewrite the factorization into a simple m^2 term. For example, 144 = 2^4 * 3^2 = (2^2)^2 * (3^2) = (2^2 * 3)^2, using exponent laws. Alternatively, if n's prime factorization only has even powers, then:

n = p1^2b1 * ... * pr^2br, where 'bi' is a positive integer

n = (p1^b1)^2 * ... * (pr^br)^2

n = (p1^b1 * ... * pr^br)^2

These steps are reversible, so the biconditional holds. The locker door will be closed if and only if it is a perfect square, and there are 31 perfect squares between 1 - 1000, inclusive.

Throughout these steps, I found that a picture wasn't too helpful in the end since I took a more number theory-like approach. The first step was to simply find a lead based on pattern recognition which gave way to custom-made rules. After that, it was a matter of narrowing down goals, which helped me know what to look for (in this case, the tau function). Using the tau function, I was able to make inferences with it in order to simplify it into a basic rule. So basic in fact, that we can just write "open" for every door except for the perfect squares.