ankur17
A high school has a strange principal. On the first day, he has his students perform an odd opening day ceremony:
There are one thousand lockers and one thousand students in the school. The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open?
A 45
B 31
C 77
D 131
E 93
Note that a locker n will be touched by the student i if and only if i divides n.
All the lockers are closed initially. For a locker to remain closed it must be touched an even number of times. Or in other words, it must have an even number of factors. Conversely, if a locker number n has an odd number of factors, it will be open at the end of the operation.
Now consider any number which is not a perfect square. For any factor x, (n/x) is also a factor such that x*(n/x)=n and n/x is not equal to x. In other words, it is possible to pair up all possible factors, and hence the number always has an even number of factors.
Perfect squares on the other hand have an odd number of factors, as all factors are paired up except sqrt(n).
So the number of lockers remaining open will be the number of perfect squares less than or equal to 1000, and this is precisely given by square_root(1000) or the largest integer less than or equal to it.
Hence :
The answer is the largest integer less than or equal to \(\sqrt{1000}\) or 31.