You are standing in a corridor with N closed doors. The person walks by you and opens every door. Then the second person walks by and stops by every second door; If the door is open he closes it, if it is closes he opens it. The third person does the same with every third door; fourth person does the same with every fourth door and so on until N people would walk the corridor. The question to you is to tell which door is open and which is closed after that.
The approach I took trying to solve this problem was to write down all state switches for 1..16. Let’s say that 1 means door opened and 0 means door closed for simplicity.
The initial state of our system (all doors closed) would be represented in the form of an array:
After first person all door will be opened:
The second person would close even doors:
If we continue this calculation we would end up with following 16x16 matrix, there I marked in yellow then the state switch is happening.
Where the final state look like:
This pattern threw me off a little at the beginning, but after careful look on the matrix it is obvious that we have 1’s at the places there we had odd number of switches and 0’s where we had even number of switches. However, number of switches we did is actually number of divisors of a given number (count amount of yellow cells for a given column – door).
This would lead us to the solution:
The doors with numbers which has even amount of divisors will remain closed and with odd amount of divisors will be opened.
Now the question is how we can calculate if number X has odd or even number of divisors… Fortunately, Math101 comes to rescue.
If you remember, In number theory, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself.
So, for example, 4 is a perfect square, since it can be written as 2 × 2, same with 9 (3x3), 16 (4x4), etc. One of interesting properties of a square number is that it has an odd number of divisors, while other numbers have an even number of divisors. Why? Because, an integer root is the only divisor that pairs up with itself to yield the square number, while other divisors come in pairs.
Thus, in the question above the full answer would be:
The doors which are located on perfect square positions will be open, all other doors will be closed.