The first 50 natural numbers will cross a corridor that contains 50 doors numbered from 1 to 50, all of which are initially locked. The first to cross will be the number 1, the second will be the number 2, followed by the number 3, and so on, until the number 50, which will be the last to cross. As they cross the corridor, the number $n$ will carry the keys to the doors numbered with multiples of $n$. For example, the number 1 will carry the keys to all the doors, while the number 2 will carry only the keys to the doors with even numbers, and the number 25 will carry only the keys to the doors numbered 25 and 50. During their passage, each number uses the keys they possess to lock the doors that are open and unlock those that are closed.

a) Which doors will be unlocked by the number 15?

b) Show that, after the number 50 has crossed the corridor, the door numbered 10 will be unlocked while the door numbered 9 will be locked.

c) After the number 50 has crossed the corridor, which doors will be unlocked?
Solution

a) Since the multiples of 15 that are less than 50 are the numbers 15, 30, and 45, the number 15 carries the keys only for the doors numbered 15, 30, and 45. Let's analyze each of these three doors separately.

- Door 15: The divisors of 15 are the numbers 1, 3, 5, and 15. Thus, these are the numbers that will modify the state of this door. The number 1 will unlock it, while the number 3 will lock it again. Then the number 5 will unlock it, and finally, the number 15 will lock it. We conclude that this door will not be unlocked by the number 15.
- Door 30: The divisors of 30 are the numbers 1, 2, 3, 5, 6, 10, 15, and 30. Thus, the number 15 will be the seventh number to modify the state of this door. Since the door starts locked and seven is an odd number, the number 15 will unlock this door.
- Door 45: The divisors of 45 are the numbers 1, 3, 5, 9, 15, and 45. Thus, the number 15 will be the fifth number to modify the state of this door, so it will unlock it.

We conclude that the number 15 will, indeed, unlock the doors numbered 30 and 45.

b) The divisors of 10 are the numbers 1, 2, 5, and 10, so these are the only numbers that can lock or unlock the door numbered 10. It follows that this door will have its state modified exactly four times. Since it starts locked, it will end up locked.

The divisors of 9 are the numbers 1, 3, and 9. Thus, the door numbered 9 will have its state modified exactly three times. Since it starts locked, it will end up unlocked.

Observation: Let $k$ be the number of one of the doors. From the solution above, we can conclude that if $k$ has an even number of divisors, then this door will end up locked. On the other hand, if $k$ has an odd number of divisors, then this door will end up unlocked.
c) For each $k \in \{1, 2, \ldots, 50\}$, let $D(k)$ be the number of divisors of $k$. From the problem statement, we know that there are exactly $D(k)$ natural numbers that carry the key to door number $k$. It follows that the door number $k$ will have its state changed exactly $D(k)$ times. Therefore, the doors that will end up open are the doors numbered $k$ such that $D(k)$ is odd.

Fix a natural number $k$ and write its prime factorization:

$$
k = p_{1}^{\alpha_{1}} \times p_{2}^{\alpha_{2}} \times \cdots \times p_{m}^{\alpha_{m}}
$$

Any divisor of $k$ must be an element of the form:

$$
p_{1}^{\beta_{1}} \times p_{2}^{\beta_{2}} \times \cdots \times p_{m}^{\beta_{m}}
$$

where each $\beta_{i}$ is an integer chosen from $\{0, 1, \ldots, \alpha_{i}\}$. Then $D(k)$ is composed of numbers of this form.

Note that for each choice of the exponents $\beta_{1}, \beta_{2}, \ldots, \beta_{m}$, there corresponds a unique element of $D(k)$, that is, a unique divisor of $k$. We can then count the number of ways to choose the exponents $\beta_{1}, \beta_{2}, \ldots, \beta_{m}$. But since each $\beta_{i}$ must belong to the set $\{0, 1, \ldots, \alpha_{i}\}$, the total number of choices for the value of $\beta_{i}$ is equal to $\alpha_{i} + 1$. Therefore, there are

$$
(1 + \alpha_{1})(1 + \alpha_{2}) \cdots (1 + \alpha_{m})
$$

choices for the values of the exponents $\beta_{1}, \beta_{2}, \ldots, \beta_{m}$, and as a consequence,

$$
(1 + \alpha_{1})(1 + \alpha_{2}) \cdots (1 + \alpha_{m})
$$

divisors of the number $k$.

For $k$ to have an odd number of divisors, it is sufficient and necessary that each of the factors $\alpha_{i} + 1$ be an odd number, that is, that $\alpha_{i}$ be even.

This shows that $k$ has an odd number of divisors if and only if $k$ is a perfect square. Therefore, the doors that remain open are precisely those numbered:

$$
1, \quad 4, \quad 9, \quad 16, \quad 25, \quad 36 \text{ and } 49
$$