A Very interesting door problem [duplicate]

Question

My teacher asked me a question which is as follow:

There are $1000$ doors numbered $1$ to $1000$, and there are $1000$ men numbered $1$ to $1000$.

Firstly $1$ numbered man goes and open all the doors.

Secondly $2$ numbered man goes and close the doors which are numbered multiple of $2$

Third $3$ numbered man goes and changes the state of doors which are numbered multiple of $3$

For example he closes the door numbered $3$ and opens the door numbered $6$

So after the man numbered $1000$ came back from his work,how many and which doors would be remain opened?

I thought about it for one hour, but couldn't get anything.

My teacher told me that there is a simple & pure mathematical logic behind this

Can you help me with this??

Answer 1

You have to notice that ODD operations means door is open and EVEN operations means door is closed. You can get it with the help of a simple example.

For example: The door number $10$ will be firstly opened by first man and then closed by $2$nd man and then opened by $5$th man and at last closed by $10$th man.

So, what mathematical logic working here is that:

If the door's number have odd number of factors then it will remain opened and If the door's number have even number of factors then it will be closed at last.

To calculate the number of factors of a number we use the formula $(a+1)(b+1)(c+1).....$ where a,b,c are powers of prime factors of number. Notice that if the number is a perfect square then a,b,c... are all even hence the number of factors ($(a+1)(b+1)(c+1).....$ ) are odd. And if the number is not a perfect square then one of a,b,c... will be odd and hence the number of factors ($(a+1)(b+1)(c+1).....$ ) will become even. So, the perfect square number doors will remain opened.

Or door number $1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961$ will remain opened ($31$ among all).

Answer 2

One thing we can do is to let the first $10$ students go do their open/ shut thing with the lockers. The students who come after them are not going to touch lockers $1-10$, so we can see which ones in that first batch are still open and try to guess the pattern.

When we do that, we find that lockers $1, 4,$ and $9$ are open and the others are closed. Now, that isn't much to go on, so maybe you could let the next $10$ students go do their thing. Then the first $20$ lockers are through being touched, and we find that lockers $1, 4, 9,$ and $16$ are the only ones in the first $20$ that are still open. So what is the pattern?

Let's take any old locker, like $48$ for example. It gets its state altered once for every student whose number in line is an exact divisor of $48$. Here is a chart of what I mean:

 Student number     leaves locker 48

      1                open
      2                shut
      3                open
      4                shut
      6                open
      8                shut
     12                open
     16                shut
     24                open
     48                shut

Notice that $48$ has an even number (ten) of divisors, namely $1,2,3,4,6,8,12,16,24,48$. So the locker goes open-shut-open-shut ... and ends up shut. Any locker number that has an even number of divisors will end up shut.

Which numbers have an odd number of divisors? That's the answer to this problem. Just to help you along, here are the locker numbers up to $100$ that are left open:$$1,4,9,16,25,36,49,64,81,100.$$

See if you can describe these numbers in a different way from "having an odd number of divisors." Think about multiplying numbers together. When you understand how to describe them, you will see that $31$ of the $1000$ lockers are still open.

Answer 3

In the end, the state of a door reflects the parity of its number of divisors.

For example, the door number $20$ is opened by $1$, closed by $2$, opened by $4$, closed by $5$, opened by $10$ and closed by $20$.

The number of divisors of an integer is the product of the multiplicities of its prime factors plus one.

In the case of $20=2^2\cdot5$, this is $3\cdot2=6$, an even number.

So a door is closed in the end for all numbers that have at least one prime factor with an odd multiplicity. Conversely, it is open in the end if all factors have an even multiplicity, hence when the number is a perfect square.

Answer 4

The simplest logic I've found is that every natural number $n$ can be represented as $n=p\cdot q$ where $p,q\in\Bbb{N}$ and $p,q\leq n$. Therefore, as the $p$-numbered man closes/opens the door numbered $n$, then the $q$-numbered man comes and revert it back, and no matter how many times the door was closed/opened, they always cancel each other. Thus, at the end all doors has to be closed, except for those doors that their corresponding number $n$ had two identical $p$ and $q$ factors (i.e., squares) for which the $p$-numbered and the $q$-numbered men were actually the same person and hence no reversion occurred. Since there are only $31$ squares between $1$ and $1000$ (including $1$), only $31$ doors corresponding to the squares will be left open.

Note: However the representation is not unique, i.e., you may find multiple such representations for a given $n$ (for example, for $n=6$ there are two different representations $6=1\cdot6=2\cdot3$), but factors $p$ and $q$ are unique for each other (they won't be repeated in other representations).