Open Close Open Close!

Number Theory Level 3

There are 100 rooms in an hotel named as $R_{1},R_{2},..,R_{100}$ . Also there are 100 men namely $M_{1},M_{2},...,M_{100}$ .

Initially all the rooms are locked. Now go by the passage

$M_{1}$ opens up all the doors from all the rooms.
$M_{2}$ closes all the rooms namely $R_{2},R_{4},...R_{100}$ .
$M_{3}$ closes up all the rooms namely $R_{3},R_{9},...R_{99}$ but opens all the doors namely $R_{6},R_{12},...R_{96}$ which were closed by the others.

This process continues till the 100th man.

Find the number of doors which are open at the last.

Clarification

$R_{n}$ will open all the doors $R_{m}$ if m is a multiple of n, but the condition is the opened doors(by others) must be closed by him.

Not original, and original was not explained so well.

Can you generalize for n men and n room?

The answer is 10.

2 solutions

Md Zuhair
Sep 27, 2017

Say that $M_{n}$ comes. Now he will 1st open/close $R_{n}$ , then $R_{2n}$ and so on.

Now $M_{1}$ opened all. So now if even number of times the work is done, the doors will be opened at last.

Take for example $M_{4}$ . Now $M_{4}$ will open/close the last time, after him no one will touch the 4th door. So His work matters.

Now initially 1st man opened all, So 4th room opened, then 2nd again closed it, Now 4th again opened it.

So if it has odd number of divisors (including 1 and 4 as seen by above example) hence it is open at the last.

Now we know number of divisors = $(a_{1}+1)(a_{2}+1)...(a_n+1)$ if $a_1,a_2,..a_n$ are the powers of the prime factos.

So for $d(n)= (a_{1}+1)(a_{2}+1)...(a_n+1)$ to be odd, each of $a_1,a_2,..a_n$ must be even which only comes if the number is perfect square.

So from 1 to 100, $1^2,2^2,..10^2$ are all perfect squares.

So all these 10 rooms will be open after the process ends.

Ahmed Almubarak
Sep 27, 2017

Each room will be open by the men who's has the number which is one of the room number factor. e.g room number 12 will be open/close by men numbers 1,2,3,4,6,12. Initially all rooms were closed, so if an odd number of men get to a room the room will be opened in the last status. But if an even number of men get to a room the room will remain closed. (O,C,O,C,O,C,.....) ......... now we know that no numbers has an odd factors but the perfect squares. So the rooms has a perfect square number will be open. How many perfect square less than or equal to 100? Answer is sqrt(100) = 10. So for any given number of room (n), the numbers of the opened room (m) will be m=(int(sqrt(n))..

Yeah, Some kind like that ..

I did like this...

Say that $M_{n}$ comes. Now he will 1st open/close $R_{n}$ , then $R_{2n}$ and so on.

Now $M_{1}$ opened all. So now if even number of times the work is done, the doors will be opened at last.

Take for example $M_{4}$ . Now $M_{4}$ will open/close the last time, after him no one will touch the 4th door. So His work matters.

Now initially 1st man opened all, So 4th room opened, then 2nd again closed it, Now 4th again opened it.

So if it has odd number of divisors (including 1 and 4 as seen by above example) hence it is open at the last.

Now we know number of divisors = $(a_{1}+1)(a_{2}+1)...(a_n+1)$ if $a_1,a_2,..a_n$ are the powers of the prime factos.

So for $d(n)= (a_{1}+1)(a_{2}+1)...(a_n+1)$ to be odd, each of $a_1,a_2,..a_n$ must be even which only comes if the number is perfect square.

So from 1 to 100, $(1^,2^2,..10^2$ are all perfect squares. So all these 10 rooms will be open after the process ends.

So how was my solution?

Md Zuhair - 3 years, 8 months ago

Yeah, just like that ...

Ahmed Almubarak - 3 years, 8 months ago

Open Close Open Close!

The answer is 10.

2 solutions

0 pending reports