Problem: Let $n\ge 2$ be an integer,
and let $a_1, a_2, \dots , a_n$ be positive integers.
Show that there exist positive integers $b_1, b_2, \dots, b_n$
satisfying the following three conditions:
\begin{enumerate}[(a)]
  \ii $a_i\le b_i$ for $i=1, 2, \dots, n$;
  \ii the remainders of $b_1$, $b_2$, \dots, $b_n$
  on division by $n$ are pairwise different,
  \ii $b_1 + \dots + b_n \le n \left( \frac{n-1}{2}
  + \left\lfloor \frac{a_1 + \dots + a_n}{n} \right\rfloor \right)$.
\end{enumerate}

Solution: Note that if $a_i > n$,
we can replace $a_i$ with $a_i-n$ and $b_i$ with $b_i-n$,
and nothing changes.
So we may as well assume $a_i \in \{1, \dots, n\}$ for each $i$.

We choose our $b_i$'s in the following way.
Draw an $n \times n$ grid and in the $i$th
column fill in the bottom $a_i-1$ cells red.
We can select $b_i$ by marking $n$ cells,
one in each row or column.
If we chose $j$th lowest row in the $i$th column,
then we would set $b_i = j$ on non-red cells
and $b_i = j + n$ on red cells.

In this way, define the \emph{penalty} $p$ as
the number of selected cells which are red.
Then
\[ b_1 + \dots + b_n = (1+2+\dots+n) + n \cdot p
  = n \cdot \frac{n-1}{2} + n \cdot (p+1).  \]
and we seek to minimize the penalty $p$.
\begin{center}
  \begin{asy}
  size(8cm);
  fill( (1,0)--(1,2)--(2,2)--(2,3)--(4,3)--(4,4)--(5,4)--(5,0)--cycle, palered);
  for (int i=0; i<=5; ++i) {
    draw((i,0)--(i,5), gray);
    draw((0,i)--(5,i), gray);
  }
  draw(scale(5)*unitsquare);
  label("$b_i \equiv 1 \pmod 5$", (0,0.5), dir(180), lightblue);
  label("$b_i \equiv 2 \pmod 5$", (0,1.5), dir(180), lightblue);
  label("$b_i \equiv 3 \pmod 5$", (0,2.5), dir(180), lightblue);
  label("$b_i \equiv 4 \pmod 5$", (0,3.5), dir(180), lightblue);
  label("$b_i \equiv 5 \pmod 5$", (0,4.5), dir(180), lightblue);
  label("$a_1-1$", (0.5,0), dir(-90), lightred);
  label("$a_2-1$", (1.5,0), dir(-90), lightred);
  label("$a_3-1$", (2.5,0), dir(-90), lightred);
  label("$a_4-1$", (3.5,0), dir(-90), lightred);
  label("$a_5-1$", (4.5,0), dir(-90), lightred);
  label("$b_1$", (0.5, 3.5), blue);
  label("$b_2$", (1.5, 2.5), blue);
  label("$b_3$", (2.5, 4.5), blue);
  label("$b_4$", (3.5, 0.5), blue);
  label("$b_5$", (4.5, 1.5), blue);
  \end{asy}
\end{center}
But the expected penalty of a \emph{random} permutation
is the red area divided by $n$, which is \[ \mathbb E[p] = \frac{(a_1-1) + \dots + (a_n-1)}{n} \]
and so there exists a choice for which
the penalty is at most $\left\lfloor \mathbb E[p]  \right\rfloor$.
This gives the required result.

\begin{remark*}
The visual aid can be excised from the solution;
which can then be rewritten more tersely as follows.
After assuming $1 \le a_i \le n$ for each $n$,
pick a uniformly random permutation $\sigma$ on
$\{1, \dots, n\}$ and define
\[ b_i =
  \begin{cases}
    n + \sigma(i) & a_i > \sigma(i) \\
    \sigma(i) & \text{otherwise}.
  \end{cases}
\]
As before $\mathbb E[e_\sigma] = \sum_{i=1}^n \frac{a_i-1}{n}$
and the rest is the same.
\end{remark*}