All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Opening doors (Posted on 2002-05-01)
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)

 See The Solution Submitted by levik Rating: 3.5000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 More Detailed Solution Comment 12 of 12 |
(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
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information