The Locker Problem

 Full disclosure; I've seen this problem (or some variant of it) before.

Let's call opening/closing a locker "affecting" a locker, and let's observe which lockers the first few students affect.

Student 1 affects lockers 1, 2, 3, ...

Student 2 affects lockers 2, 4, 6, ...

Student 3 affects lockers 3, 6, 9, ...

So, in general, student n will affect all lockers which are multiples of n.

Now, let's consider some locker m. Whether or not locker m is open or closed at the end of the process depends on how many times it gets affected. Since all lockers start open, then if it is affected an even number of times, it will remain open. Otherwise, it will be closed.

Suppose n is a factor of m. Then there exists an integer k such that kn = m. Since m is a multiple of n, it will be affected by student n. Note that m is also a multiple of k, and will be affected by student k as well!

Suppose instead that n is not a factor of m. Then m is not a multiple of n, and so will not be affected by student n.

Hence, locker m is affected by student n exactly when n is a factor of m. Thus, the state of locker m at the end of the process depends entirely on its number of factors. More specifically, it depends on whether it has an even or an odd number of factors!

Consider some factor n of m. Then there exists a unique integer k such that kn = m. As well, since nk = m, we also have that k is a factor of m, and that n is the unique integer which when multiplied by k equals m.

By considering each factor of m in this way, we can pair up all factors of m as (n_1, k_1), (n_2, k_2), ..., (n_r,, k_r). Let's only consider positive factors (since m is positive.) For example, we can pair up the factors of 12 as (1, 12), (2, 6), and (3, 4).

Now we're approaching the answer. You can imagine how for each pair (n_i, k_i), students n_i and k_i both affect locker m and "cancel" each other out. However, we haven't considered what happens yet when n_i = k_i. Being careful, and with a little more work, we will find the correct answer.

First, let's prove that any distinct pairs (n_i, k_i) and (n_j, k_j) share no numbers between them. Let's suppose to the contrary that they do. Let's say that without loss of generality, n_i = n_j. But then 

(n_i)(k_i) = m = (n_j)(k_j)

implies (n_i)(k_i) = (n_i)(k_j)

implies k_i = k_j

implies (n_i, k_i) = (n_j, k_j), which is a contradiction of the pairs being distinct. Hence, no distinct pairs share any numbers.

It's possible could have a pair with a repeated value, i.e. (n_i, n_i). Suppose there are multiple distinct pairs with repeated values, say (n_i, n_i) and (n_j, n_j). But then we get

(n_i)^2 = m = (n_j)^2

implies n_i = n_j (since these are positive integers)

implies (n_i, n_i) = (n_j, n_j), which is again a contradiction of distinctness.

What this tells us is that if we consider the factor pairs (n_1, k_1), (n_2, k_2), ..., (n_r,, k_r) for m, each pair contains factors found in no other pair, and at most one of the pairs contains a repeated factor. 

It should hopefully be clear that the parity of the number of factors of m depends squarely (haha) on whether or not there is a pair with a repeated factor. If there is one; what does that mean? Suppose (n_i, n_i) is such a pair. Then (n_i)^2 = m, which means that m is a perfect square! Conversely, if m is not a perfect square, then no such pair exists.

Finally, if m is a perfect square, then it will have 2(number of pairs - 1) + 1 factors (since it has a pair with a repeated factor), which is an odd number. Hence, if m is a perfect square, then locker m will be closed at the end of the process! If m is not a perfect square, then it will have 2(number of pairs) factors, which is even, and so locker m will be open.

This gives us our answer. Taking a step back to think about the problem more generally, it's all about pairing up factors of m. Most of the time, when locker m is affected by student n, we can consider this to be "cancelled" by student k affecting locker m, where kn = m. This holds true if every case except for when n^2 = m, since student n will only affect locker m once. For this reason, the only closed lockers at the end of the process will be the lockers which are perfect squares.

Most of the strategy I used when solving this problem revolved around simplifying the problem wherever possible (changing closing/opening to "affected", reducing lockers and students to numbers and their factors, realizing that you only need to know about the parity of the number of factors for a locker) and looking at small examples, checking for patterns, and trying to generalize behaviour from them (what happens for the first couple students?). Had I not known about the problem before, I likely would have checked what happens with the first few lockers and noticed that 1 and 4 end up closed while 2 and 3 remain open, which I may have recognized as having something to do with perfect squares.