A permutation of the integers 1 to 2022 is a sequence $\sigma=\left(\sigma_{1}, \ldots, \sigma_{2022}\right)$ such that each element of the set $\{1, \ldots, 2022\}$ is equal to exactly one term $\sigma_{i}$. What is the smallest possible value that the sum

$$
\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\ldots+\left\lfloor\frac{a_{2022}}{2022}\right\rfloor
$$

can take when the integers $a_{1}, a_{2}, \ldots, a_{2022}$ form a permutation of the integers from 1 to 2022?
In general, let $\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ denote the sum

$$
\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\ldots+\left\lfloor\frac{a_{n}}{n}\right\rfloor,
$$

and let $\mathcal{S}_{n}$ be the smallest value that $\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ can take when the integers $a_{1}, a_{2}, \ldots, a_{n}$ form a permutation of the integers from 1 to $n$.
Given such a permutation, let $k$ be the integer such that $a_{k}=n$. Then, for every integer $i \leqslant k$, let $b_{i}$ be the rank of the integer $a_{i}$ within the set $\left\{a_{1}, \ldots, a_{k-1}\right\}$, i.e., the number of indices $j \leqslant k-1$ for which $a_{j} \leqslant a_{i}$. Since $a_{i} \geqslant b_{i}$, we observe that

$$
\begin{aligned}
\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{n}\right) & \geqslant\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\ldots+\left\lfloor\frac{a_{k}}{k}\right\rfloor \\
& \geqslant\left\lfloor\frac{b_{1}}{1}\right\rfloor+\left\lfloor\frac{b_{2}}{2}\right\rfloor+\ldots+\left\lfloor\frac{b_{k-1}}{k-1}\right\rfloor+\left\lfloor\frac{n}{k}\right\rfloor \\
& \geqslant \mathcal{S}_{k-1}+\left\lfloor\frac{n}{k}\right\rfloor,
\end{aligned}
$$

with the convention that $\mathcal{S}_{0}=0$.
Furthermore, if $a_{1}, a_{2}, \ldots, a_{k-1}$ is a permutation of the integers from 1 to $k-1$ for which $\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{k-1}\right)=\mathcal{S}_{k-1}$ and if we set $a_{i}=i-1$ for all $i \geqslant k+1$, we have

$$
\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{n}\right)=\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\ldots+\left\lfloor\frac{a_{k-1}}{k-1}\right\rfloor+\left\lfloor\frac{n}{k}\right\rfloor=\mathcal{S}_{k-1}+\left\lfloor\frac{n}{k}\right\rfloor .
$$

We deduce that $\mathcal{S}_{n}=\min \left\{\mathcal{S}_{k-1}+\lfloor n / k\rfloor: 1 \leqslant k \leqslant n\right\}$.
We will now prove by induction on $n$ that $\mathcal{S}_{n}=\left\lceil\log _{2}(n+1)\right\rceil$ for all integers $n \geqslant 0$, which will allow us to assert that $\mathcal{S}_{2022}=\left\lceil\log _{2}(2023)\right\rceil=11$.
Indeed, this is true for $n=0$. Now let $n$ be a non-zero natural number, and let $k$ be an integer such that $1 \leqslant k \leqslant n$ and $\mathcal{S}_{n}=\mathcal{S}_{k-1}+\lfloor n / k\rfloor$. If we set $\lambda=\lfloor n / k\rfloor$, we observe that $k>n /(\lambda+1)$ and that

$$
2^{\lambda}=\sum_{i=0}^{\lambda}\binom{\lambda}{i} \geqslant\binom{\lambda}{0}+\binom{\lambda}{1}=1+\lambda
$$

so that

$$
\mathcal{S}_{n}=\mathcal{S}\left(a_{1}, a_{2}, \ldots, a_{n}\right) \geqslant \mathcal{S}_{k-1}+\lfloor n / k\rfloor \geqslant \log _{2}(k)+\lambda>\log _{2}\left(2^{\lambda} n /(\lambda+1)\right) \geqslant \log _{2}(n)
$$

This means that $2^{\mathcal{S}_{n}}>n$, or equivalently, $2^{\mathcal{S}_{n}} \geqslant n+1$, hence $\mathcal{S}_{n} \geqslant\left\lceil\log _{2}(n+1)\right\rceil$.
Conversely, let $k=\lceil(n+1) / 2\rceil$ and $\ell=\left\lceil\log _{2}((n+1) / 2)\right\rceil$. Since $(n+1) / 2 \leqslant 2^{\ell}$, we also know that $k \leqslant 2^{\ell}$, so

$$
\mathcal{S}_{n} \leqslant \mathcal{S}_{k-1}+\lfloor n / k\rfloor=\left\lceil\log _{2}(k)\right\rceil+1 \leqslant \ell+1=\left\lceil\log _{2}(n+1)\right\rceil,
$$

which concludes the induction.
Comment from the graders: The problem was difficult, and many students claimed to have a complete solution incorrectly. Many candidates only treated specific cases, or did not prove their claims, which can result in losing many points.
Be sure to justify all your claims: it is better to spend a little more time on a problem and solve it completely, rather than trying to get points on a more difficult problem (which clearly was not successful on problem 7).