Question

1,000 students march slowly through their school, going past 1,000 lockers. The first student opens every locker along the way. Then the second student comes along and shuts every second locker. Then the third student reverses the condition of every third locker, and then the fourth student reverses the condition of every fourth locker. The students continue in this manner (e.g., the 99th student reverses the condition of every 99th locker, etc.). After all students have gone through the school, which lockers remain open?

Answer 1

This is a puzzle for people who enjoy them, not a homework question, so no points unless you provide your reasonings!

Answer 2

Before i give a detailed solution, i would like to verify my answer (not sure if its correct). Is it 31 lockers will be open?

Answer 3

It is correct.

Answer 4

Sweet, ok, so i went through a lot of ideas to solve this. First i created a matrix that represented "transformation" of the lockers. Letting each locker have a value of -1 in the start to signify being closed, I let each kid come by and if they reversed the status of the locker, they in effect would multiply by -1. This can be simulated in matrices by having a 1000 x 1000 matrix similar to the identity matrix, except if you are switching the status of every kth locker, every kth 1 down the diagonal has to be negative, all the other 1s postive. So basically, you want to compute the product of 1000 of these matrices whose entries are either 1or -1 along the diagonal.

Answer 5

Now, while that is somewhat doable, then I started thinking about how many times each locker would get hit. If i just look at the kth locker, how many times will it get tagged? Well, it will get tagged every time a divisor of k comes up. For example:
the 26th locker will get tagged on the 1st, 2nd, 13th, and 26th run
Now looking at the problem in that angle, we see if k has an even number of divisors, overall it would be changed when everything is done. Its only when k has an odd number of divisors where we get the change. An the only way an integer can have an odd number of divisors is if the integer is a perfect square.
Therefore to solve the problem, you just need to count how many perfect squares there are from 1-1000, and there are 31.

Answer 6

er, typo,if k has an even number of divisors, it wouldnt* be changed

Answer 7

Nice work! You can also forego the counting by taking \(\sqrt{1000}\) and rounding down.