Puzzle - 100 Doors

Problem Statement - 

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in the following way: 

In the first walk, the person toggles every door 

In the second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, … 

In the third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, … 

Likewise,

In the 100th walk, the person toggles the 100th door. 

Which doors are open in the end? 

Solution - 

Approach - We'll try to solve this question mathematically

First we understand that each door state will be changed, depending on its number of factors and to be closed at the end the number of factors of that particular number should be odd.

For eg:- Door 1 will be open at end as its only factor is 1 (odd), Door 2 will be closed as it has factors 1&2 (even).

Now, let us consider a number x which can also be written as a multiplication of the power of primes i.e. x = 2^a * 3^b * 5^y ..... (so on)

F(No. of factors of x) = (a+1)(b+1)(c+1)...

For F to be odd (a+1), (b+1), (c+1).. should be odd (because of multiply by even F will turn out to be even).

=> If a+1 is odd, that means a is even.

∴ x = (2^a՛ * 3^b՛ * 5^y՛ ..... )^2 (because a = 2a՛, b = 2b՛...)

This can also be written as x = y^2  { y : y is a natural number }

From this we can infer that all squares of natural number have odd factors.

∴ 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 door number will be open at the end as the are square of 1,2,3,4,5,6,7,8,9 and 10.