Locker Room & Strange Principal

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 asked 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?

What principal was trying to teach? 

Source 

The Lesson Taught By Strange Principal

Where it did begin? 

While finding the solution we need to keep basic fact from the problem in mind. Since lockers were closed initially, the lockers which are 'accessed' for odd number of times only are going to open. Rest of all would be closed.

Now task is to find how many such lockers are there which were 'accessed' for odd number of times.

Let's take any number say 24 for example, which is not perfect square & find out how many factors it has.

24 = 1 x 24
24 = 2 x 12
24 = 3 x 8
24 = 4 x 6

So factors are 1,2,3,4,6,8,12,24 i.e. 8 numbers as factors which is even number. Every factor is paired with other 'unique' number! So this pairing always makes number of factors 'even'. In the problem, this lock no.24 will be 'accessed' by 1st, 2nd, 3rd..................24th student. That means 'accessed' even number of time & hence would remain closed.

Now let's take a look at lock no. 16 in which 16 is perfect square. Finding it's factors,

16 = 1 x 16
16 = 2 x 8
16 = 4 x 4

we get 1,2,4,8,16 i.e. 5 numbers as factors which is odd. The reason behind is here 4 appears twice (with itself) while rest of others are paired with other 'unique' number. Hence, number of factors of a perfect square are always odd. Now here lock 16 would be accessed by 1st, 2nd, 4th, 8th, 16th i.e. 5 times. Hence it will be open.

Like this way, every lock with number which is perfect square would be 'accessed' for odd number of times & hence would remain open! e.g. 1,4,9,16,25,49 & so on.

Now 961 (31^2) is the maximum perfect square that can appear within 1000 (32^2) as 1024 goes beyond.

Hence there would be 31 locks open while rest of all closed!

Lesson Of The Day

So what lesson taught by strange principal? The number which is perfect square has odd number of divisors.