Tuesday, April 3, 2012

Lockers...

Generally you don't inspired with every puzzle that you solve. Every body would have seen handful of puzzles that made them elevated fore few moment. All of them will introduces something new to us. It is not the feeling of solving the puzzle makes a puzzle solver excited instead the wisdom it brought in indeed make it more thrilling experience. Here is the one such puzzle...



There are 1000 lockers in a high school with 1000 students. The problem begins with the first student opening all 1000 lockers; next the second student closes lockers 2,4,6,8,10 and so on to locker 1000; the third student changes the state (opens lockers closed, closes lockers open) on lockers 3,6,9,12,15 and so on; the fourth student changes the state of lockers 4,8,12,16 and so on. This goes on until every student has had a turn. How many lockers will be open at the end?



Locker 1 will remain open for sure
Locker 2 will be closed (opened by 1 and closed by 2)
Locker 3 will also be closed
Locker 4 will be open (opened by 1, closed by 2 and opened by 4)
Locker 5 - closed (1-5)
Locker 6 - closed ( 1-2-3-6)
Locker 7 - closed (1-7)
Locker 8 - closed (1-2-4-8)
Locker 9 - open (1-3-9)

One can easily come to a below conclusion by looking at the above iterations,

 numbers have even number of factors will be closed at the end and numbers having odd number of factors will remain open.


 Now, the question is to get the list of numbers having odd number of factors. The below points are obvious when it comes to factors of a number

1. every number has at least two factors (1 and the number itself)
2. every factor can be paired with another factor in such a way that multiplying both the factor will be the number itself
    For instance, number 6 has four factors, 1,2,3 and 6
              here 1 can be paired with 6, 2 can be paired with 3.

3. Total number of factors will be even if the paired factors are not same.

In other words the number of factors are not even if any of the pairs have the same numbers ( for instance 2,2 for 4).

if a factor pair contains the same number then the number must be a perfect square :).
Also a number can not have two such factor pairs with identical number (which is obvious).

Hence number of lockers those remain open will be perfect squares (perfect is not it :) ).
So total number of lockers remain open is 31 (31^2 =961, 32^2= 1024 ).