I am planning on taking an interview in the near future and was practicing on some previously asked aptitude questions. During my prep I came across a problem for which I couldn't find an answer.
Problem:
There is a school with 100 students and correspondingly 100 lockers, all of which start off closed. The first student opens every locker and the second students closes every other locker starting with the second (2,4,6...etc..) . The 3rd student changes the state of the lockers numbered (3,6,9.. etc.). The fourth student changes the state of the lockers numbered (4,8,12.. etc..).. This continues until all the 100 students passes along the lockers.. when all the 100 student is done which locker is closed and which locker is in open condition?
Problem Breakdown:
Let's say there the initial state is the state before student 1 opens all lockers and the lockers reach their final state after the 4th student changes the lockers.. Since there are 100 students(100 % 4=0) the state of the lockers after the student 4 works on it will be equal to the state of the lockers after the 100th student changes the state ( I hope the assumption is right!!!)
My approach to the solution:
I took the first 10 lockers and checked how each locker's state will be after all 4 students have operated on it. I was hoping to find a pattern and here is my result..
Open Lockers: 1,4,5,6,7,8
Closed Lockers: 2,3,9,10
There is no recognizable pattern in this 10 lockers.
Help:
I just need to know is there some formula or theorem that can be applied to these type of problems in general and please show an example of how that particular formula can be applied to this problem. If such formula is not available then please tell me how this problem can be solved?
Lets say there are $n$ students numbered $1,2,3...,n$. The lockers which are opened an odd number of times will remain open till the end. The student $i$ interacts with locker $j$ if $i|j$. Thus lockers having odd number of divisors will remain open till the end. Since only perfect squares have odd number of divisors. The number of open lockers is $[\sqrt n]$.