Imagine a row of 100 closed doors. Now, make 100 passes along the row, and at each pass "toggle" the doors whose number is divisible by the number of the pass. (By "toggle", we mean to open a closed door, or close an opened one.)

For example, on the first pass, we will toggle all the doors, on the second, we will toggle only the even-numbered doors, on the third - only doors whose number is divisible by three, and so on.

At the end of the 100 passes, how many doors will be left open?

(from techInterview.org)

(In reply to answer by K Sengupta)

At the outset, we observe that the doors that are toggled an even number of times will remain open and the doors that are toggled an odd number of times will remain closed.

Let us consider door #R, for 1<= R <= 100, where R is not a perfect square. Let us choose integers x and y, with 1<= x< y<= R, such that x*y = R. Since y*x = R = x*y, it follows that the total number of factorization of R will be even. Accordingly, the door number R will be toggled an even number of times. Therefore, door number R will remain closed.

Now if R is a perfect square, so that R = p^2, for some positive integer p, then for all the factorizations of the form x*y = R = y*x, for unequal x and y,  we have to add the extra factorization R = p*p. Thus, the total number of factorization of R will always be odd whenever R is a perfect square. It may be observed that for the trivial case R = 1, there is no factotization of the form x*y = R = y*x, with only the factorization R = p*p, for p=1. Accordingly, the door number R will be toggled an odd number of times. Therefore, door number R will remain open.

We now observe that there are precisely 10 perfect squares between 1 and 100 inclusively, and consequently, exactly 10 doors will remain open.

Posted by K Sengupta on 2008-06-05 03:27:46