Determine ${ }^{1}$ the smallest value that the expression

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

can take, where $a_{1}, a_{2}, \ldots, a_{2022} \geq 1$ are real numbers such that $\left|a_{i}-a_{j}\right| \geq 1$ for all $1 \leq i<j \leq 2022$.
Note: For a real number $x$, $\lfloor x\rfloor$, called the floor of $x$, denotes the greatest integer not greater than $x$.
From the premise, it follows that the smallest of the numbers $a_{1}, a_{2}, \ldots, a_{2022}$ is at least 1, the second smallest is at least 2, and so on, up to the 2022nd, which must be at least 2022. If we now replace the numbers $a_{1}, \ldots, a_{2022}$ successively by $1,2, \ldots, 2022$ in order of size, the sum from the problem statement will not increase. We thus see that we may restrict ourselves to the case where $\left(a_{1}, a_{1}, \ldots, a_{2022}\right)$ are pairwise distinct positive integers. Now we replace 2022 with an arbitrary positive integer $k$ and claim that the smallest value $s(k)$ that the sum

$$
\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{k}}{k}\right\rfloor
$$

can take, when $a_{1}, a_{1}, \ldots, a_{k}$ are pairwise distinct positive integers, is exactly $\left\lfloor\log _{2}(k)\right\rfloor$.

- Lower Bound: Since $m$ is evidently monotonically increasing, it suffices to show that $m\left(2^{t}\right) \geq t$ holds. The case $t=0$ is clear, for $t>0$ we use induction and assume $m\left(2^{t-1}\right) \geq t-1$ as known. Let $a_{1}, a_{1}, \ldots, a_{2}$ be arbitrary pairwise distinct positive integers. Then the maximum $a_{i}$ of these numbers is at least $2^{t}$. If $i>2^{t-1}$, then
$\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t}}}{2^{t}}\right\rfloor \geq\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t-1}}}{2^{t-1}}\right\rfloor+\left\lfloor\frac{a_{i}}{i}\right\rfloor \geq m\left(2^{t-1}\right)+1=t-1+1=t$
If, however, $i \leq 2^{t-1}$, then the set $X=\left\{1,2, \ldots, 2^{t-1}\right\} \backslash\left\{a_{1}, a_{2}, \ldots, a_{2^{t-1}}\right\}$ is not empty. Let $b \in X$ be arbitrary. Then $a_{i} \geq 2^{t}=2^{t-1}+2^{t-1} \geq b+i$, so
$\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t}}}{2^{t}}\right\rfloor \geq\left\lfloor\frac{a_{1}}{1}\right\rfloor+\cdots+\left\lfloor\frac{b+i}{i}\right\rfloor+\cdots+\left\lfloor\frac{a_{2^{t-1}}}{2^{t-1}}\right\rfloor+\geq m\left(2^{t-1}\right)+1=t-1+1=t$
- Upper Bound: We set

$$
a_{i}=\left\{\begin{array}{l}
i-1, \text { if } i \text { is not a power of two, } \\
2^{s+1}-1, \text { if } i=2^{s} .
\end{array}\right.
$$

Then $a_{1}, a_{2}, \ldots, a_{k}$ are pairwise distinct positive integers and it holds that

$$
\left\lfloor\frac{a_{i}}{i}\right\rfloor=\left\{\begin{array}{l}
0, \text { if } i \text { is not a power of two, } \\
1 \text { otherwise. }
\end{array}\right.
$$

Thus, $\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{k}}{k}\right\rfloor=\left\lfloor\log _{2}(k)\right\rfloor$.
Applied to the specific situation of the problem statement, we obtain that the smallest value that the given sum can take is $\left\lfloor\log _{2}(2022)\right\rfloor=11$.

[^0]
## NATIONAL

MATHEMATICS COMPETITIONS
Education & Talent

# Selection Competition for the International Mathematical Olympiad 2022

## Example Solutions and Hints for the 2nd Selection Test