1
$\begingroup$

In a row there are 'n' room , whose door no. are 1,2,...n, initially all doors are closed. A person takes n round of the row, numbers as 1st round, 2nd round,....nth round. In each round he interchange the position of those door no. whose number is multiple of round no. Find out after nth round ,How many doors will be open.

The answer is √n

My approach let n be 4. Let C=Closed, O=Open

Inital:-CCCC

ROUND 1:OOOO

ROUND 2:OCOC

ROUND 3:OCCC

ROUND 4:OCCO

HENCE after 4 round we 2 open viz √4=2

This indicate that my apprach is corect but want to formulate it. Please help me

$\endgroup$
3
$\begingroup$

You can figure out that for any given door, say door #38, you will visit it for every divisor it has.

It has 1 & 38, 2 & 19. so on pass 1 i will open the door, pass 2 i will close it, pass 19 open, pass 38 close. For every pair of divisors the door will just end up back in its initial state.

Lets now take door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.

Number of perfect squares from 1 to n is $\lfloor{\sqrt{n}}\rfloor$ and this is your answer

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.