Two hundred students enter a hall filled with lockers numbered . The first student opens all the lockers. The second operates lockers . The third operates on and so on.
In short; if the locker was open then the student closes it and if it was closed then opens it.
Initially if all lockers were closed then at the end of these operations, how many lockers remain open?
This question belongs to the set Number theory best problems
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
We will begin by observing the events.
After the first student operates, all lockers are opened.
After the second student operates, lockers with numbers 2 , 4 , 6 , 8 , . . . . . . . . . , 2 0 0 are closed again.
After the third student operates, lockers with numbers 3 , 9 , 1 5 , 2 1 , . . . . . , 1 9 5 are closed and lockers with numbers 6 , 1 2 , 1 8 , 2 4 . . . . . . . , 1 9 8 are opened again.
So we observe that the lockers with locker no.s having odd positive factors remain open, and those having even factors remain closed after all operations.
So we need to find no.s with odd factors.
If the no. k can be represented as p 1 n 1 × p 2 n 2 × p 3 n 3 × . . . . . . . . . . . . . . . . . . . . . . . .
then the no. of factors is ( n 1 + 1 ) × ( n 2 + 1 ) × ( n 3 + 1 ) × . . . . . . . . . . . . . . . . . . . . . . . . which will be odd when ( n 1 + 1 ) , ( n 2 + 1 ) , ( n 3 + 1 ) . . . . all are odd.
Thus n 1 , n 2 , n 3 . . . . . all should be even.
If n 1 , n 2 , n 3 . . . . . are all even then k must be perfect square.
So, we conclude that all lockers with locker no.s a perfect squares are all open after all operation.
And there are 1 4 perfect squares till the no. 2 0 0 . So the answer is 1 4