Exercise 7. Find all integers $n \geqslant 1$ for which there exist $n$ integers $a_{1}, \ldots, a_{n}$ such that $a_{i}$ is the number of elements divisible by $i$ among $a_{1}, \ldots, a_{n}$.
Solution to Exercise 7: Let $n, a_{1}, \ldots, a_{n}$ be integers satisfying the property given in the statement. We can start by noting that $a_{i} \leqslant n$ since there are at most $n$ elements among $a_{1}, \ldots, a_{n}$ divisible by $i$ for any $i$.

We then establish a double counting of the number of pairs $(i, a_{k})$ such that $i$ divides $a_{k}$. On the one hand, for a fixed $a_{k}$, the number of integers $i$ in $\{1, \ldots, n\}$ that divide $a_{k}$ corresponds to $d(a_{k})$, the number of divisors of $a_{k}$. The number of pairs $(i, a_{k})$ such that $i$ divides $a_{k}$ is therefore $d(a_{1}) + \ldots + d(a_{k})$. On the other hand, for a fixed $i$, the number of $a_{k}$ such that $i$ divides $a_{k}$ is precisely $a_{i}$. The number of pairs is therefore $a_{1} + \ldots + a_{n}$.

This double counting can in fact be summarized by the following interchange of sums: denoting $1_{i \mid a_{k}}$ the number which is 1 if $i$ divides $a_{k}$ and 0 otherwise, we have

$$
\sum_{i=1}^{n} a_{i} = \sum_{i=1}^{n} \sum_{k=1}^{n} 1_{i \mid a_{k}} = \sum_{k=1}^{n} \sum_{i=1}^{n} 1_{i \mid a_{k}} = \sum_{k=1}^{n} d(a_{k})
$$

Now, we have the inequality $d(x) \leqslant x$ for all integers $x$, with equality if and only if $x=1$ or 2 (indeed, if $x \geqslant 3, x-1$ and $x$ are coprime, so $x$ has at most $x-1$ divisors). We deduce from the obtained equality that each of the $a_{k}$ is 1 or 2.

But $a_{1} = n$ by definition, so $n=1$ or $n=2$.

- If $n=1$, then $a_{1}=1$ satisfies the property given in the statement.
- If $n=2$, then $a_{1}=2$ and $a_{2}=1$ satisfy the property given in the statement.

The integers $n$ sought are therefore $n=1$ and $n=2$.

Solution $n^{\circ} 2$:

First, note that each $a_{i}$ is strictly positive. Indeed, according to the statement, since $a_{i}$ is the number of $k$ between 1 and $n$ such that $i$ divides $a_{k}$, we have $a_{i} \geqslant 0$ for all $i$. If furthermore $a_{i}=0$, then $i$ divides $a_{i}$, so $a_{i} \geqslant 1$, which would be absurd. We therefore know that each of the $a_{i}$ is strictly positive. Let's show that we necessarily have $n \leqslant 2$. For this, let's reason by contradiction and suppose $n \geqslant 3$.

Let's make some observations: we have $a_{1}=n$ because 1 divides each $a_{i}$. Moreover, $a_{n-1}>0$ so there exists $k$ such that $a_{k}$ is divisible by $n-1$. Since $0 < a_{k} \leqslant n$, we have $a_{k} = n-1$.

Let $j$ be an integer such that $a_{j}$ is divisible by $n$. Since $0 < a_{j} \leqslant n$, we have $a_{j} = n$. Therefore, $j$ divides all the $a_{k}$, so $j$ divides $a_{1}=n$ and $a_{k}=n-1$, so $j$ divides $n-(n-1)=1$, so $j=1$.

Since $a_{1}=n$, we have $a_{n}=1$. Furthermore, since $a_{k} \neq a_{1}$, we have $k \neq 1$ so $k$ does not divide $a_{n}$. We deduce that $k$ divides all the $a_{i}$ except $a_{n}$. Since $a_{k}=n-1 \neq a_{n}$, we have $k \neq n$, so $k$ divides $a_{1}-a_{k}=1$, so $k=1$ which is contradictory.

We thus deduce that $n=1$ or 2 and we obtain that these two $n$ are solutions in the same way as in the first solution.

Comment from the graders: The exercise is very well done by the few students who tackle it.