0

Here is the problem: There are 100 doors and 100 people. The doors have two states (open/closed). All the doors are closed at first. Then the first person opens all the doors, the second person toggles the doors in multiples of 2 (e.g. door 2,4,6..). The third person toggles the doors in multiples of 3 (3,6,9...). This continues until person 100 toggles the door 100. So how many doors are open and how many are closed?

I understood this part that 1st person will open the door, second person will close the door, third person will open the door and so on.. But how to solve it?

YuiTo Cheng
  • 4,705
Coder Singh
  • 15
  • Hint: simply write out the answer for the first few doors (do the first $20$ doors, say). That is, note that $1$ is open (as it is opened by the first person and thereafter untouched), $2$ is closed (opened by the first closed by the second), and so on. The pattern will become clear. – lulu Mar 03 '17 at 16:05
  • Answer is square of numbers but how? @lulu – Coder Singh Mar 03 '17 at 16:06
  • If $n=\prod p_i^{a_i}$ then the number of divisors of $n$ is $\prod (a_i+1)$. – lulu Mar 03 '17 at 16:08

2 Answers2

0

If a door is closed at the end, it must have an even number of factors. In fact, all numbers except for perfect squares have an even number of factors. Hence the doors with these numbers will remain open. Only the squares of 1 to 10 are below hundred. Hence 10 doors are open.

0

A door will be open if an odd number of people toggle it--this is to say, if its number has an odd number of divisors. This is true iff the door's number is a perfect square (since, given $n$, a divisor $a$ of $n$ can be "paired up" with $n/a$; if $n$ is not a perfect square, then we will always have $n/a \neq a$). Thus, there are $10$ open doors and $90$ closed doors at the end.

florence
  • 12,819