## Wednesday, October 10, 2007

### Solution to 100 Lockers Puzzle

Solution to the 100 Lockers Puzzle.
Those who haven't seen the puzzle yet, give it a try at 100 Lockers Puzzle
Student 1 opens all the lockers and Student 2 goes and closes every second locker
and so on... means
Locker 1: No one change the state of 1st locker except student 1 so it is in opened state.
Locker 2: Student 1 opens and Student 2 closes.
Locker 3: Student 1 opens and Student 3 closes.
Locker 4: Student 1 opens, Student 2 closes and Student 4 Opens.
. . .
This is very tedious approach and no one likes to do this physical exercise.

But by observing clearly we can conclude
Locker 1 state can be changed by one student,
Locker 2 state can be changed by two students,
Locker 3 state can be changed by two students,
Locker 4 state can be changed by three students, ...
which clearly clarifies that the Lockers are Opened only by the Odd number of students.

We can get the count of students who are going to the particular locker by finding the factors of that locker.

If we get odd number of factors then that locker is in Opened State.
For Example:
Locker 9 has factors {1,3,9} -> odd count, so it is in opened state.
So there are 10 Lockers which has an odd count. And they are {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}.

Another simple way to get how many lockers has an odd number of factors. That is by just calculating the perfect squares from 1 to 100. So, they are nothing but {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}.
---