A Warden Killing The Boredom

A warden oversees an empty prison with 100 cells, all closed. Bored one day, he walks through the prison and opens every cell. Then he walks through it again and closes the even-numbered cells. On the third trip he stops at every third cell and closes the door if it’s open or opens it if it’s closed. And so on: On the nth trip he stops at every nth cell, closing an open door or opening a closed one. At the end of the 100th trip, which doors are open?

'These' special cells will have doors open!

Similar Puzzle! 

Open Doors in an Empty Prison!

Read the story behind the title!

Let's take few cells into consideration as representatives.

The warden visits cell no. 5 twice - 1st & 5th trip.1 & 5 are only divisors of 5.

He visits cell no. 10, on 1st, 2nd, 5th, 10th trips i.e. 4 times. Here, divisors of 10 are 1,2,5,10.

He stops cell no. 31 only twice i.e. on 1st and 31st trip.

He visits cell no.25 on 1st, 5th, 25th trips that is thrice.

In short, number of divisors that cell number has, decides the number of visits by warden.

For example, above, cell no.5 has 2 divisors hence warden visits it 2 times while 10 has 4 divisors which is why warden visits it 4 times.

But when cell number is perfect square like 16 (1,2,4,8,16) or 25 (1,5,25) he visits respective cells odd number of times. Otherwise for all other integers like 10 (1,2,5,10) or like 18 (1,2,3,6,9,18)  or like 27 (1,3,9,27) he visits even number of time.

For prime numbers, like 1,3,5,....31,...97 he visits only twice as each of them have only 2 divisors. Again, number of visits is even.

Obviously, the doors of cells to which he visits even number of times will remain closed while those cells to which he visits odd number of time will remain open.

So the cells having numbers that are perfect square would have doors open. That means cells 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 would be having their doors open.

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.