1

My friend gave me a question. The question states:

There a $100$ people named $(1,2,3,.....,100)$ and there are $100$ doors named $(1,2,3,...,100)$ .Assume all doors are closed. The first named $1$ person comes and opens the doors which are multiples of $1$. The only functions that a person can do is open a door which is already closed or closed a door which is already open. Now the person named $2$ comes and does this function(of opening or closing) on all the doors which are multiples of 2. This process similarly takes place for $3,4,.....100$ . At the end when this completed how many doors will be left which will be open and not closed.

My thoughts in this question were that I was thinking the only doors which will be open will be the squares because:

$$\begin{array}{|c|c|} N&\text{factors}\\ 4&1,2,4\text(factors)\\ 9&1,3,9\text(factors)\\ 16&1,2,8,4,16\text(factors)\\ 25&1,5,25\text(factors)\\ 36&1,3,6,18,2,12,36,4,9\text(factors)\\ 49&1,7,49\text(factors)\\ 64&1,2,4,8,16,32,64\text(factors)\\ 81&1,3,9,27,81\text(factors)\\ 100&1,2,5,4,10,25,20,50,100\text(factors)\\ \end{array}$$

So as we can see when each of these numbered people will go the doors will open and be closed respectively which will end up all of the squares being open. But how do I show that these are the only numbers?

Also this seems to be a tedious way to do it and doesn't seem like this will be this tedious. So is there any way which is better than this.

  • 2
    Door $n$ will be open if and only if $n$ has an odd number of (positive) divisors. – Daniel Fischer Oct 06 '15 at 12:59
  • 1
    Squares are the only ones which have an odd number of factors. So your thinking us absolutely right. This is also the famous locker problem. – Shailesh Oct 06 '15 at 12:59

1 Answers1

1

As Daniel Fischer remarked, door $n$ will be open if and only if $n$ has an odd number of divisors. Divisors usually come in pairs: If $k\mid n$, then also $\frac nk\mid n$, and vice versa. The only way to have an odd number of divisors is thus if the case $k=\frac nk$ occurs. Writing this as $k^2=n$ shows that a number has an odd number of divisors if and only if it is a square.

joriki
  • 238,052