Exercise 9. Find the integers $n$ for which the equality

$$
\sum_{i=1}^{n} \sum_{j=1}^{n}\left\lfloor\frac{i \times j}{n+1}\right\rfloor=\frac{n^{2}(n-1)}{4}
$$

is satisfied.

We recall that, for any real number $x$, the notation $\lfloor x\rfloor$ denotes the floor of $x$, that is, the greatest integer less than or equal to $x$.
Solution to Exercise 9 For any integer $k$, we denote $r_{n+1}(k)$ as the remainder of the Euclidean division of $k$ by $n+1$, that is, the smallest natural number such that $n+1$ divides $k-r_{n+1}(k)$. The double sum on the left can then be rewritten as

$$
\begin{aligned}
\mathcal{S} & =\sum_{i=1}^{n} \sum_{j=0}^{n} \frac{i j-r_{n+1}(i j)}{n+1} \\
& =\frac{1}{n+1}\left(\sum_{i=1}^{n} i\right)\left(\sum_{j=0}^{n} j\right)-\frac{1}{n+1} \sum_{i=0}^{n} \sum_{j=0}^{n} r_{n+1}(i j) \\
& =\frac{1}{n+1} \frac{n(n+1)}{2} \frac{n(n+1)}{2}-\frac{1}{n+1} \sum_{i=0}^{n} \sum_{j=0}^{n} r_{n+1}(i j) \\
& =\frac{n^{2}(n+1)}{4}-\frac{1}{n+1} \sum_{i=0}^{n} \sum_{j=0}^{n} r_{n+1}(i j)
\end{aligned}
$$

It is therefore necessary to find the integers $n$ for which

$$
\sum_{i=1}^{n} \sum_{j=0}^{n} r_{n+1}(i j)=(n+1)\left(\frac{n^{2}(n+1)}{4}-\frac{n^{2}(n-1)}{4}\right)=\frac{n^{2}(n+1)}{2}
$$

Let $i$ be an integer, and let $d=\operatorname{PGCD}(i, n+1)$ and $k=(n+1) / d$ and $\ell=i / d$. The integers $k$ and $\ell$ are coprime, so the $k$ integers $0, \ell, 2 \ell, \ldots,(k-1) \ell$ represent the $k$ residues modulo $k$, and the $k$ integers $0, i, 2 i, \ldots,(k-1) i$ represent the $k$ residues $0, d, 2 d, \ldots,(k-1) d$ modulo $n+1=k d$. In particular, for any integer $t$, we know that

$$
\sum_{j=k t}^{(k+1) t-1} r_{n+1}(i j)=\sum_{j=0}^{k-1} j d=d \frac{k(k-1)}{2}
$$

so that

$$
\sum_{j=0}^{n-1} r_{n+1}(i j)=\sum_{t=0}^{d-1} \sum_{j=k t}^{(k+1) t-1} r_{n+1}(i j)=d^{2} \frac{k(k-1)}{2}=\frac{(n+1)(n+1-d)}{2}
$$

In particular,

$$
\sum_{j=0}^{n-1} r_{n+1}(i j) \leqslant \frac{n(n+1)}{2}
$$

with equality if and only if $d=1$, so if $i$ and $n+1$ are coprime. Thus,

$$
\sum_{i=1}^{n} \sum_{j=0}^{n} r_{n+1}(i j) \leqslant \frac{n^{2}(n+1)}{2}
$$

with equality if and only if $n+1$ is coprime with each of the integers $1,2, \ldots, n$, that is, if $n+1$ is a prime number.

In conclusion, the integers sought are the integers $n$ such that $n+1$ is prime.

$\underline{\text { Alternative Solution } n^{\circ} 1}$ In the following, we set $s_{i, j}=i j /(n+1)$ and $\mathcal{S}_{i}=\sum_{j=1}^{n}\left\lfloor s_{i, j}\right\rfloor$. For all $j \leqslant n$, we note that $s_{i, j}+s_{i, n+1-j}=i$. Consequently, if we set $s_{i, j}=k+x$ with $k$ an integer and $0 \leqslant x<1$, we deduce that

$$
\left\lfloor s_{i, j}\right\rfloor+\left\lfloor s_{i, n+1-j}\right\rfloor=\lfloor k+x\rfloor+\lfloor(i-k-1)+(1-x)\rfloor=i-1+\lfloor 1-x\rfloor
$$

so that $\left\lfloor s_{i, j}\right\rfloor+\left\lfloor s_{i, n+1-j}\right\rfloor \geqslant i-1$ with equality if and only if $x \neq 0$, that is, if $n+1$ does not divide $i j$.

Now, when $j$ runs through the set $\{1,2, \ldots, n-1\}, n+1-j$ also runs through this set. We deduce that

$$
2 \mathcal{S}_{i}=\sum_{j=1}^{n}\left\lfloor s_{i, j}\right\rfloor+\left\lfloor s_{i, n+1-j}\right\rfloor \geqslant \sum_{j=1}^{n}(i-1)=n(i-1)
$$

with equality if and only if $n+1$ does not divide any product $i j$, that is, if $n+1$ is coprime with $i$. We then conclude that

$$
\mathcal{S}=\sum_{i=1}^{n} \mathcal{S}_{i} \geqslant \frac{n}{2} \sum_{i=1}^{n}(i-1)=\frac{n^{2}(n-1)}{4}
$$

with equality if and only if $n+1$ is coprime with all integers $i$, that is, if $n+1$ is a prime number.

Thus, the integers $n$ sought are exactly those for which $n+1$ is prime.

Graders' Comment The exercise was difficult, and few students managed to make progress. A real challenge was to convince oneself that there exist arbitrarily large integers $n$ for which the statement is true. Here, working through small cases gave a good intuition of the solutions, but many cases had to be considered. Consequently, many students tried to use inequalities to show that, when $n$ was arbitrarily large, the sum would become larger or smaller than $n^{2}(n-1) / 4$. Given the solution to this exercise, this strategy was unfortunately doomed to fail.

Students who solved the problem did so as in Solution 2, whose main trick is not unlike the solution to Problem 16 of the Animath Fall Cup: it is important to read the solutions to problems not solved, as they can help advance in very different problems.