Test of Mathematics Solution Subjective 177 -The Famous Doors Problem

This is a Test of Mathematics Solution Subjective 177 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

 There are 1000 doors $ D_1, D_2, . . . , D_{1000}$ and 1000 persons $ P_1, P_2, . . ., P_{1000}$. Initially all the doors were closed. Person $ P_1$ goes and opens all doors. Then person $ P_2$ closes doors $ D_2, D_4, . . ., D_{1000}$ and leaves all odd numbered doors open. Next, $ P_3$ changes the state of every third door, that is, $ D_3, D_6, . . ., D_{999}$ by closing a door if it is open or opening a door if it is closed. Similarly, $ P_m$ changes the state of the doors $ D_m, D_{2m}, . . ., D_{nm}$, while leaving the other doors untouched. Finally, $ P_{1000}$ opens $ D_{1000}$ if it is closed or closes it if it is open. At the end how many doors remain open?

Solution

This particular problem requires careful analysis of the problem statements and decide what the problem is exactly asking us to solve.

Basically there are two possible states of the door, namely Open (denote by 'o') and Close (denote by 'c'), and initially all doors are in state 'c'.  Let us define the operation of changing the state of the door by  'F'. So if 'F' can be seen as a function where the variables are 'o' and 'c'  and we have:

F(o) = c

F(c) = o

So if a door is operated on 'n' times we represent it by $ F^n(c)$ as initially all the doors were closed. It is very trivial to state that if the door is operated even number of times it returns to the 'c' state and if it's operated odd number of times then it has a change to 'o' state.

Therefore, $ F^n(c)$ = c, if n is even, else $ F^n(c)$ = o, if n is odd.       ......(i)

As 'n' represents the number of times the operation has been performed on a particular door, as we understand from the problem that a door $ D_m$ is only operated by a person $ P_k$ iff k divides m. So whenever we have an divisor of 'm', we increment the value of 'n' by 1. Thus finally after all the counting the value of 'n' will be nothing but the number of divisors of 'm'.

We are to find which doors will remain in state 'o' after the whole procedure and for a door to be in state 'o' it has to be operated odd number of times (from (i)). Which implies that 'n' has to be odd. So all those doors which have odd number of divisors will be open after the process.

Now it can be shown very trivially that a number has odd number of divisors iff it is a perfect square. (Think!!)

So our solution will be all those doors that are marked with perfect square numbers ranging from 1 to 1000.

Solution Set: {$ D_1, D_4, D_9, D_{16}, D_{25}, . . ., D_{900}, D_{961}$}