Mad Teacher

Number Theory Level 2

A mad teacher had 100 students in his class. Once he took them to the playground and brought 100 boxes which could be opened and closed. When he brought the boxes, all of them were closed. He ordered the 1st boy to open all the boxes. So, the 1st boy opened them. Then he ordered the 2nd to close the 2nd, 4th, 6th, 8th..... numbered boxes. Next he told the 3rd boy to open(if closed box found) and close(if opened box found) the 3rd,6th,9th........boxes. Thus, when all of the boys finished, how many boxes will remain opened?

The answer is 10.

1 solution

Shenal Kotuwewatta
Apr 10, 2015

Notice that the box $n$ changes its state $\sigma_0(n)$ times, where $\sigma_0(n)$ denotes the number of positive divisors of $n$ . So for the box $n$ to be open, $\sigma_0(n)$ should be odd.

Unless $n$ is a perfect square, every factor $a_i$ of $n$ has a corresponding factor $b_i$ such that $a_i \cdot b_i = n$ making $\sigma_0(n)$ even.

If $n$ is a perfect square, every factor $a_i$ except $\sqrt{n}$ has a corresponding factor $b_i$ such that $a_i \cdot b_i = n$ so $\sigma_0(n)$ is odd.

Since there are exactly $10$ perfect squares from $1$ to $100$ , the answer is $\boxed{10}$ .

Mad Teacher

The answer is 10.

1 solution

0 pending reports