1. Home >
2. Apps >
3. Groups >

# Count Doors

Question asked by pradeep_agrawal in #Coffee Room on Jun 30, 2009
pradeep_agrawal · Jun 30, 2009
Rank C2 - EXPERT
There are 1000 rooms (numbered from 1 to 1000) and 1000 persons (also numbered from 1 to 1000).

Assume that all doors are closed at first.

1. First person will open all the doors.
2. Second person visits all doors whose number is divisible by 2. And on those rooms he will close the door if it is open and open the door if it is close.
3. Third person visits the doors whose number is divisible by 3. And on those rooms he will close the door if it is open and open the door if it is close.
.
.
.

4. 1000th person visits the door having 1000 number (because that’s the only door whose number is divisible by 1000). He will open the door if it is close and he will close the door if it is open.

Find the number of doors that will be open at end of above process. Explain the logic behind the result.

Posted in: #Coffee Room
tech_vaibhav_ee · Jul 1, 2009
Rank D1 - MASTER
31 doors...
maths behind it:no. of perfect squares b\w 1 and thousand...
logic: the no. of factors of a no. is always a even no. unless it is a perfect square..and the door is open by those people whose no. are factor of the door to be opened...
pradeep_agrawal · Jul 1, 2009
Rank C2 - EXPERT
tech_vaibhav_ee, you are really good at puzzle solving.

Both the answer and the explanation given above is correct.

shalini_goel14 · Jul 1, 2009
Rank A3 - PRO
Sorry, I couldn't get the explanation, can anyone explain it CLEARLY again ?
vishnu priya · Jul 1, 2009
Rank B2 - LEADER
I also join with shalini.I too did not understand it clearly.
pradeep_agrawal · Jul 1, 2009
Rank C2 - EXPERT
Let me explain the logic behind the solution.

A person can visit a door only if the door number is completely divisible by the number associated with the person. In other word we can say that, a door can be visited by only by persons whose number completely divides the door number.

The number of person visiting any door will be equal to the number of factors of that door number, e.g., consider door number 10, there are four factors of number 10 (i.e., 1, 2, 5, and 10) and thus the door number 10 can be visited by four person with number 1, 2, 5, and 10.

Lets consider opening a door or closing a door as one operation.

As initially all the doors are close, so a door will be in open state at the end if it has been operated odd number of times (1, 3, 5, ...), i.e., odd number of people have visited the door.

Now odd number of people will visit a door if door has odd number of factors.

If we do some mathematics we will find that only the numbers which are perfect square of some other number have odd number of factors (e.g., 25 has 3 factors as 1, 5, and 25) and all other numbers have even number of factors.

So only those doors will be in open state whose number is a perfect square of some other number. Now there are only 31 such numbers between 1 to 1000 (1, 4, 9, 16, 25 ... 900, 961) so 31 doors will be in open state.