The 1000 Locker Problem

 

A school has 1000 students and 1000 lockers. On the first day of school all lockers are open.
Student #1 closes all lockers.
Student #2 opens each second locker.
Student #3 changes the state of each third locker
. . .
And so on until all 1000 students have had their turn.

After all 1000 lockers are done, which lockers are open? Which lockers are close? Why?

Strategy:  From understanding of the problem, we find out necessary mathematical objects to represent it. Using our knowledge, experience and employment of some creativity and experiments we simulate the problem mathematically. In this case, knowledge of integers, vectors and element-wise multiplication, use of indexing together with patience take us to the first formulation.

During the process, we realize that a key concept is the divisibility. This leads to the second formulation without using vector.

After reviewing the number theory, the second formulation is turned into a simpler third formulation using number of divisor function.

Finally, we find a proven fact that number of divisors function is odd if argument is perfect square. This leads to the 4th method. 

The problem includes two states (closed, opened) of each locker, and an action that changes the state from one to another. In this approach, we think about how to represent these two states, and the action by mathematical objects we have. From the knowledge of integer numbers we know that

（-1）（1）=  -1，  （-1）（-1）= 1

This allows us to test with

There are 1000 lockers and 1000 students. We need a container system to store the information which allows element-wise multiplication. We look into our knowledge and find that vectors would work. We do ‘element-wise product’ to perform the student operation. We now attempt an experiment.

At the very beginning, the state of the lockers is (all lockers opened):

Student 1 changes the states of each 1st locker. This operation can be represented by a ten-vector whose elements are -1. After the operation, the state of the lockers is a vector element-wise product: 

Student 2 changes the state of each 2nd locker. This operation can be represented by a ten-vector whose every 2nd element is -1. After the operation, the state of the lockers is the vector element-wise product:

Below table shows the first 100 lockers' states and a generalization that can be applied to 1000 lockers case