EGMO 2019 Problem 5

(Netherlands).

Let $n \geq 2$ be an integer, and let $a_{1}, a_{2}, \ldots, a_{n}$ be positive integers. Show that there exist positive integers $b_{1}, b_{2}, \ldots, b_{n}$ satisfying the following three conditions:

1). $a_{i} \leq b_{i}$ for $i=1,2, \ldots, n$; 2). the remainders of $b_{1}, b_{2}, \ldots, b_{n}$ on division by $n$ are pairwise different; and 3). $b_{1}+\cdots+b_{n} \leq n\left(\frac{n-1}{2}+\left\lfloor\frac{a_{1}+\cdots+a_{n}}{n}\right\rfloor\right)$. (Here, $\lfloor x\rfloor$ denotes the integer part of real number $x$, that is, the largest integer that does not exceed $x$.)