Let $r = (a_1 + a_2 + \dots + a_n) \pmod{n}$, and let $d_i = b_i - a_i$. Then we have $$b_1 + b_2 + \dots + b_n \leq n\left(\frac{n - 1}{2} + \frac{a_1 + a_2 + \dots + a_n - r}{n}\right)$$$$\iff$$$$d_1 + d_2 + \dots + d_n = (b_1 - a_1) + \dots + (b_n - a_n) \leq \frac{n(n - 1)}{2} - r$$ So now we can see the problem as follows: We have a vector $(a_1, a_2, \dots, a_n)$ in $\mathbb{Z}_n^n$ and we're allowed to make a move that adds $1$ to one of the coordinates. We want to prove that we can make all the coordinates distinct in at most $\frac{n(n - 1)}{2} - r$ moves. Notice that a trivial way to attain this is to fix a vector $v = (v_1, v_2, \dots, v_n)$ with all distinct coordinates and gradually transform $a_i$ into $v_i$. Consider doing this for all $n$ choices of $v$ which are rotations of $(0, 1, 2, \dots, n - 1)$. By looking at the moves that we perform at each coordinate we can see that we perform $$n\left(\frac{n(n - 1)}{2}\right)$$ Moves in total, so one of these rotations uses at most $\frac{n(n - 1)}{2}$ moves. But by considering the sum modulo $n$ we see that every valid sequence must use a number of moves congruent to $\frac{n(n - 1)}{2} - r \pmod{n}$, since at the end the sum is $0 + 1 + \dots + n - 1 \equiv \frac{n(n - 1)}{2} \pmod{n}$ and at the start it is $r$. So this choice in fact uses at most $\frac{n(n - 1)}{2} - r$ moves, as desired.

The key idea is quite simple.

Cute/fun problem. (But not really number theory.) 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$. Pick a uniformly random permutation $\sigma$ on $\{1, \dots, n\}$ and define \[ b^\sigma_i = \begin{cases} n + \sigma(i) & a_i > \sigma(i) \\ \sigma(i) & \text{otherwise}. \end{cases} \]In that case, $\sum_i b^\sigma_i = (1+\dots+n) + n e_\sigma$, where $e_\sigma$ is the number of indices $i$ with $a_i > \sigma(i)$. Note that \[ \mathbb E[e_\sigma] = \sum_{i=1}^n \frac{a_i-1}{n} \]by linearity of expectation. Thus there is some choice of $\sigma$ with $e_\sigma \le \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

Wow this was a not too complicated but yet nice problem... who proposed this?

v_Enhance wrote: Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works. This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$, and for other cases where the righthand side is 0.

ubermensch wrote: Wow this was a not too complicated but yet nice problem... who proposed this? I have heard that is has been proposed by Poland but I do not know the author.

prague123 wrote: v_Enhance wrote: Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works. This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$, and for other cases where the righthand side is 0. Typo, I meant $\le$ there.

First, zero-index the sequences (i.e. so they are \(a_0,\ldots, a_{n-1}\) and \(b_0,\ldots b_{n-1}\)). Moreover, we prove the general case where \(a_i,b_i\) are nonnegative. Note that if the problem holds for some \(a_i\), we can perform the following invertible operations to prove it for a modified \(a_i\): - We can sort/reorder the \(a_i\) by symmetry. - We can add/subtract \(1\) from each \(a_i\) and \(b_i\) - this increases/decreases each side of the inequality in \(C\) by \(n\), and maintains everything else. - We can add/subtract \(n\) from one of the \(a_i\) and \(b_i\) - similar reason. Claim: We can modify any \(a_i\) such that \(a_i\le i\) for all \(0\le i\le n-1\). This clearly solves the problem, as we can just set \(b_i=i\) for all \(0\le i\le n-1\), then invert the process (sidenote: this appears wrong because it gives the bound \(\le n(n-1)/2\), but the transformation utilizes the "breathing space"). First, we can force everything to be \(\le n-1\) by subtracting by the appropriate factors of \(n\). Moreover, we can sort the integers and shift down accordingly so that \(0=a_0\le a_1\le \ldots\le a_{n-1}\le n-1\). Now, consider the following process, assuming that there exists \(a_i>i\). We claim that \(\sum_{k=0}^{n-1}a_k-k\) is strictly decreasing. Let \(i\) be the minimum number such that \(a_{i}>i\) (note \(i\neq 0\)). Shift the subsequence \(a_0,\ldots, a_{i-1}\) to the right by \(n-i\), then add \(n\), such that the new sequence is \(a_i, a_{i+1},\ldots, a_{n-1}, a_{0}+n, a_{1}+n, \ldots, a_{i-1}+n\). Redefining the indices, we can see that \(a_k-k\) has now increased by \(i\) for each \(k\), because if originally \(k\ge i\), then \(k\) had been shifted to the left by \(i\), and if originally \(k<i\), then \(k\) had been shifted to the right by \(n-i\) but \(a_k\) had been increased by \(n\). Thus, the sum has increased by \(in\). Now, we subtract what was originally \(a_i>i\) from every index. This decreases the sum by \(a_in\). Thus, each step of this process decreases the desired sum by \(n(a_i-i)\), while maintaining the fact that the numbers are between \(0\) and \(n-1\). Assuming that the process can be carried out infinitely, \(\sum_{k=0}^{n-1}a_k-k\) is eventually small enough so that we force one of \(a_i\) to be negative, contradiction. Thus, the process must eventually stop, so that \(a_i\le i\) for all \(i\), as desired.

First, construct the $b_i$ one after the other as follows: Let $b_i\in \{a_i, a_i+1, \ldots, a_i+(i-1)\}$ such that the remainder of $b_i$ modulo $n$ is not equal to any remainder of the previously constructed $b_1, b_2, \ldots, b_{i-1}$ (pigeonhole principle forces this to work). If there are multiple choices, pick arbitrarily. We claim the constructed set satisfies the conditions of the problem. Indeed, for all $i$, define $c_i=b_i-(i-1)$. By our construction, $c_i\leq a_i$ and $n\;|\;c_1+c_2+\ldots+c_n$ , therefore \begin{align*} b_1+b_2+\ldots+b_n&=c_1+c_2+\ldots+c_n+\frac{n(n-1)}{2}\\ &=n\left(\frac{n-1}{2}+\left\lfloor\frac{c_1+c_2+\ldots+c_n}{n}\right\rfloor\right)\\ &\leq n\left(\frac{n-1}{2}+\left\lfloor\frac{a_1+a_2+\ldots+a_n}{n}\right\rfloor\right), \end{align*} as desired.

Here is the same solution I posted earlier, but phrased in a way that I think is more natural (albeit longer), and also how I actually thought about the problem when I was solving it. Hopefully more instructive. 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 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$. [asy][asy]defaultpen(fontsize(8pt)); 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), grey); draw((0,i)--(5,i), grey); } 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); [/asy][/asy] But the expected penalty of a 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 $\lfloor \mathbb E[p] \rfloor$. This gives the required result.

Let $x_i=b_i-a_i$. We want $\{x_i+a_i\}$ to be a complete residue system modulo $n$. To this end, pick a uniformly random permutation \[\sigma:[n]\to\mathbb{Z}/n\mathbb{Z},\]and pick $x_i$ to be the smallest non-negative number such that $x_i+a_i\equiv \sigma(i)\pmod{n}$. We see that $x_i$ has an equal chance to be any of $0,\ldots,n-1$, so \[\mathbb{E}(x_i)=\frac{n-1}{2}.\]Thus, \[\mathbb{E}(x_1+\cdots+x_n)=\frac{n(n-1)}{2},\]so there exists a valid choice of the $x_i$s such that \[x_1+\cdots+x_n\le\frac{n(n-1)}{2}.\]However, we have that \[\sum a_i+\sum x_i\equiv 0+\cdots+(n-1)=\frac{n(n-1)}{2}\pmod{n},\]so $\sum x_i=\frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right)+kn$ for some integer $k$. Thus, we see that in fact, the $x_i$s we chose must further satisfy \[\sum x_i\le \frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right).\]Adding $\sum a_i$ to both sides yields the desired conclusion.

Relabel $a_n, b_n$ as $a_0, b_0$. WLOG $0 \le a_i \le n-1$ for all $i$, and further WLOG $a_0 \le a_1 \le \ldots \le a_{n-1}$. We use a simple greedy algorithm. For $0 \le i \le n-1$, select $b_i$ to be the smallest number such that $b_i \ge a_i$ and $b_i \not \equiv b_{i-1}, \ldots, b_0$. Since only $i$ of the $b_j$ have been selected already, clearly we will have $b_i \le a_i + i$. Summing this across all $i$, we have $b_0 + b_1 + \ldots b_{n-1} \le a_1 + a_2 + \ldots + a_{n-1} + 1 + 2 + \ldots + n-1$, which is almost (but not quite) what we want. However, we can do better. Since $b_0, \ldots, b_{n-1}$ is a permutation of $0, \ldots, n-1 \pmod{n}$, $b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1}$ is a multiple of $n$. So in fact this quantity is less than or equal to the largest multiple of $n$ which is $\le a_0 + \ldots + a_{n-1}$, i.e. $n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor$. Hence $$b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1} \le n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \implies b_0 + \ldots + b_{n-1} \le n\left( \frac{n-1}{2} + \left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \right)$$so we are done.

For each $a_i$, we define $x_i$ and $r_i$ such that $x_i n + r_i$, $0 \le r_i < n$, and $x_i$ is an integer. Consider a random permutation $\pi$ of the set $\{0, 1, \cdots , n-1\}$. We define \[\pi(a_i) = n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i),\]that is, the minimal number greater than or equal to $a_i$ congruent to $\pi(i)$ modulo $n$. Now, we consider \[\sum_{i = 1}^n \pi(a_i) = \sum_{i = 1}^n \left(n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i)\right) = \sum_{i = 1}^n \pi(i) + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil = \]\[\sum_{i = 0}^{n-1} i + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil = n\left(\frac{n-1}{2} + \sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil\right).\]It suffices to show that there exists a permutation $\pi$ such that \[\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^n a_i}{n}\right\rfloor.\]Substituting in $a_i = x_in + r_i$, we see that it suffices to show that \[\sum_{i = 1}^n \left(x_i + \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil\right) \le \sum_{i = 1}^n x_i + \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor,\]or equivalently, \[\sum_{1 \le i \le n, r_i > \pi(i)} 1 = \sum_{i = 1}^n \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor.\]Now, by the probabilistic method, it suffices to show that the expected value of $\sum_{1 \le i \le n, r_i > \pi(i)} 1$ is less than or equal to $\left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor$, since we will then have that such a permutation $\pi$ exists. We compute that \[\mathbb{E}\left[\sum_{1 \le i \le n, r_i > \pi(i)} 1\right] = \sum_{i=1}^n\mathbb{P}[r_i > \pi(i)] = \sum_{i=1, r_1 \ge 1}^n\frac{r_i - 1}{n} = \frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n} - 1 \le \]\[\left\lfloor\frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n}\right\rfloor = \left\lfloor\frac{\sum_{i=1}^n r_i}{n}\right\rfloor.\]Thus, we are done by the probabilistic method. $\blacksquare$

CantonMathGuy wrote: \[\mathbb{E}[b_1 + \dots + b_n] = a_1 + \dots + a_n + \frac{n(n-1)}{2}.\] I don't understand, I have never seen statistics used in math olympiad problems. How can you use statistics? aren't you ignoring exceptions unintentionally?

It's not statistics, it is just linearity of expectation. What does "ignoring exceptions unintentionally" mean?

Let $\pi$ be a randomly chosen permutation of $\{0,\ldots,n-1\}$. Let \[ d_i = \begin{cases} \pi_i - a_i \text{ if } \pi_i \ge a_i \\ a_i-\pi_i+n \text{ if } \pi_i < a_i. \end{cases} \]This is the smallest positive integer such that $a_i+d_i \equiv \pi_i \pmod{n}$. Since $d_i \in \{0,\ldots,n-1\}$, and $\pi$ is chosen uniformly at random, $\mathbb{E}[d_i] = \tfrac{n-1}{2}$. Let $b_i=a_i+x_i$. Then \[ \mathbb{E}\left[ \sum_{i=1}^n b_i \right] = \sum_{i=1}^n \mathbb{E}[b_i] = \sum_{i=1}^n \mathbb{E}\left[ a_i + \frac{n-1}{2} \right] = \frac{n(n-1)}{2} + \sum_{i=1}^n a_i. \]So there exists $\pi$ such that $\sum b_i \le \tfrac{n(n-1)}{2} + \sum a_i$. This is almost what we want, but not quite. We need to make $\sum a_i$ instead into the largest multiple of $n$ at most $\sum a_i$. We can sharpen the bounds using that fact that \[ \sum_{i=1}^n b_i \equiv 0+1+\cdots+(n-1) = \frac{n(n-1)}{2} \pmod{n}. \]Let $\sum a_i = qn+r$. Then we have \[ \sum b_i \le \frac{n(n-1)}{2} + qn+r \implies \sum b_i - \frac{n(n-1)}{2} - qn \le r.\]But since $\sum b_i - \frac{n(n-1)}{2} \equiv 0 \pmod{n}$, the left hand side is a multiple of $n$. It is at most $r\le n$, so it is in fact at most 0. Hence, \[ \sum b_i - \frac{n(n-1)}{2} - qn \le 0 \implies \sum b_i \le \frac{n(n-1)}{2} + nq=\frac{n(n-1)}{2} + n \left \lfloor \frac{\sum a_i}{n} \right \rfloor.\]

First change the indices from $1$ through $n$ to $0$ through $n-1$, and note that for any $i$, if $a_i>n$ then subtracting $n$ from $a_i$ doens't change anything. Thus we can WLOG let $a_0, ..., a_n\in [0, n-1]$. Now let $\pi$ be a random permutation of $(a_0, ..., a_{n-1})$ and for all $i$ replace $a_i$ with $\pi(a_i)$. For each $i$, let $b_i$ be the smallest integer at least $a_i$ such that $b_i\equiv i\pmod{n}$, so $b_k=k$ if $a_k\le k$ and $b_k=n+k$ if $a_k>k$. Thus $b_0+...+b_{n-1}=0+1+...+n-1+nP=\frac{n(n-1)}{2}+nP$, where $P$ is the number of $k$ such that $a_k>k$. Now, for each $k$, let $c_k$ be the number of $a_i$ equal to $k$, so $c_0+...+c_{n-1}=n$ and $c_1+2c_2+...+(n-1)c_{n-1}=a_0+...+a_{n-1}$. Note that for each $k$, the probability that $a_k>k$ is $\frac{c_{k+1}+...+c_{n-1}}{n}$, meaning that the expected value of $P$ is $\frac{c_1+...+c_{n-1}}{n}+\frac{c_2+...+c_{n-1}}{n}+...+\frac{c_{n-1}}{n}=\frac{c_1+2c_2+...+(n-1)c_{n-1}}{n}=\frac{a_0+...+a_{n-1}}{n}$. Thus it is possible to permute $(a_0, ..., a_{n-1})$ such that $P\le \lfloor \frac{a_0+...+a_{n-1}}{n}\rfloor$ in which case $b_0+...+b_{n-1}\le \frac{n(n-1)}{2}+n(\lfloor \frac{a_0+...+a_{n-1}}{n}\rfloor)$, so we are done.

"2019 EGMO = 2016 USACO" Reminds me of a nice usaco problem - USACO Gold Febuary 2016 contest "Circular Barn"!! We'll reformulate the problem like this, because I like cows more! First, let $\triangle_i = b_i - a_i,$ so we wish to show $$\sum \triangle_i \leq \frac{n(n-1)}{2} + n\left(\left\lfloor \frac{a_1+a_2+\cdots a_n}{n}\right \rfloor \right) - \sum_{i=1}^n a_i = \frac{n(n-1)}{2} - ((\sum a_i) \mod n)$$Thus, we can work with the $a_i \mod n$ instead. Imagine Farmer John is herding his $n$ cows (bessie being one of them!) in a circular barn. The barn has $n$ rooms in a clockwise fashion, labeled $0...n-1$. Each room $i$ currently has $c_i \geq 0$ cows, and $\sum c_i = n.$ Farmer John wishes to move the cows so that in the end, each barn has one cow. The cows may only move in clockwise order through the rooms. Farmer John wishes to minimize, over all of his $n$ cows, the total number of rooms they move. (This is the $\sum \triangle_i.$) For example, if our $a_i \mod n$ were $0,0,3,4,4$ with $n=5,$ this means to start with, Farmer John has two cows in room zero, one cow in room three, and two cows in room four in a barn with five rooms. The important insight is to notice that for any two cows $A$ and $B,$ if $A$ walks past $B$'s start point, then $A$ should end at a room before $B$'s endpoint. This is because, if $A$ walked past both $B$'s start and end points, then we could obtain a solution that's just as good by switching $A$ and $B$'s endpoints. Thus, if we are choosing between many cows to drop off at one door, we may as well choose the cow that started walking first without hurting our solution. This suggests an order in which to process the cows: we simply start at any point on the circle and begin walking all the cows at that point around the circle. We keep track of the distance walked by all our active cows, and pick up any cows we encounter along the way. At every door, we "drop a cow off" - the cow that has been walking for the longest amount of time. We have to make sure that we find a point to start at such that we always have a cow to drop off at each door, and such a point is guaranteed to exist in some optimal solution because of our insight above. (This is the well known one gallon of oil distributed around a circular track problem.) Note that in this process, no cow will get dropped off at a point past the starting point; ie. We will finish dropping all $n$ cows with the first cow at the room we started with, and the $n$-th cow at the room directly counterclockwise of the starting room. This is because we have exactly $n$ cows, and we drop off a cow at each room. An equivalent, but better way to view this algorithm, is to look at it from the last cow's point of view; ie. the last cow that gets picked up in the above process. This cow will get dropped at the room directly counterclockwise from the starting room. The second to last cow will get dropped off two rooms counterclockwise from the starting room... and so forth. Now we show that this optimal process satisfies the inequality. First, note that any cyclic shift of our indices of the rooms doesn't change the $((\sum a_i) \mod n)$ term, as we have $n$ cows. So, wlog, lets label the zero indexed room as the room we start our algorithm with. Each room's index relabels, so $a_i \rightarrow a_i'.$ With this new labeling, the last cow that gets picked up ends up at room $n-1.$ This last cow will move at most $n-1$ steps, because she starts at some index between $0$ and $n-1$ and ends up at room $n-1.$ The second to last cow ends up at room $n-2,$ and so she will move at most $n-2$ steps.... and so on until the very first cow which we just dropped off where she started at, room zero. This gives us the bound $\sum \triangle_i \leq (n-1)+(n-2)+\cdots+1+0 = \frac{n(n-1)}{2}.$ So how do we improve it with the mod term? Well, consider backtracking the process. Consider what happens if all the cows were still back at room zero. (This room zero is the starting room in our algorithm.) In this case, it takes exactly $\frac{n(n-1)}{2}$ moves, because the "last" cow will move from room zero to room $n-1,$ and so on. However, the term $(\sum a_i) \mod n = (\sum a_i') \mod n$ tells us at least how much some of the cows have already moved! If we look at the cow with the largest index, she initially had to move $n-1$ steps, but now she needs to move fewer steps. Similarly for the other cows that are not at room zero. Over all $n$ cows, with our shifted indices, we see that this term $\sum a_i'$ gives exactly how much fewer moves the cows need compared to if they had all started at room zero. Thus, it takes them at most $\frac{n(n-1)}{2} - \sum a_i' \leq \frac{n(n-1)}{2} - ((\sum a_i) \mod n)$ moves to make Farmer John happy. The end of the story. http://www.usaco.org/index.php?page=viewproblem2&cpid=621 Happy holidays!

Randomly assign each $b_i$ a distinct residue mod n, and let $b_i\in\{a_i,a_i+1,...,a_i+(n-1)\}$,$c_i=b_i-a_i<n$. We have $$\frac{\sum_i b_i}n=\mathbb{E}\sum_{i} b_i= \sum_{i} \mathbb{E}b_i = \frac{\sum_{i} a_i}n+ \mathbb{E}c_i = \frac{sum_{i} a_i}n+ \frac{(n-1)}{2},$$which is equivalent to what we want to prove since the sum of $a_i/n$ by expected value there must be some arrangement of $b_i$ where it's the largest integer smaller than the RHS (since LHS is an integer due to sum of $b_i$ divisible by n), which is indeed the FLOOR of that $a_i$ stuff; multiplying by n after that gives desired.

Wow global Let $\pi$ denote a permutation of $(0, 1, \dots, n-1)$. Let $\pi(i)$ denote the $i$-th element in this permutation (where $i$ ranges from $1$ to $n$). Now consider a random permutation $\pi_k$, where $k \in (1, 2, \dots, n!)$ denotes of the $n!$ permutations. Then let $b_i$ be the smallest number greater than $a_i$ such that $b_i \equiv \pi(i) \pmod{n}$. Denote, \begin{align*} \pi_{kb} = \sum_{i=1}^n b_i \end{align*}Then as we vary over all $k$, or all permutations, we must show, \begin{align*} \mathbb{E}[\pi_{kb}] \leq n \cdot \left(\frac{n-1}{2} + \left\lfloor \frac{a_1+ \dots + a_n}{n} \right\rfloor \right) \end{align*}Now we will compute $\mathbb{E}[\pi_{kb}]$. Consider some random $a_i$. Now lets say $a_i \equiv k \pmod{n}$. Note that $a_i$ is assigned every residue from $(0, 1, 2, \dots, n-1)$ exactly $(n-1)!$ times. Furthermore if $a_i$ is assigned a residue $r$ then $b_i - a_i$ is equal to the positive value of $r - k \pmod{n}$, ie: for $k - 1$ we would have $b_i - a_i = n - 1$. Thus we find, \begin{align*} \mathbb{E}(b_i - a_i) = \frac{1}{n} \cdot \frac{n(n-1)}{2} = \frac{n-1}{2} \end{align*}Thus our total sum over all pairs $(a_i, b_i)$ is $\frac{n(n-1)}{2}$. Now computing we have, \begin{align*} \mathbb{E}(\pi_{kb}) &= \mathbb{E}\left(\sum_{i=1}^n b_i - a_i\right) + \mathbb{E}\left(\sum_{i=1}^n a_i\right)\\ &= \frac{n(n-1)}{2} + \sum_{i=1}^n a_i \end{align*}Now noting that $b_1 + b_2 + \dots + b_n - \frac{n(n-1)}{2}$ is always an integer divisible by $n$, we can optimize slightly more (the floor part) to have that there exists some choice of the $a_i$ such that, \begin{align*} \frac{1}{n} \cdot \sum_{i=1}^n b_i \leq \frac{n-1}{2} + \left\lfloor \frac{\sum_{i=1}^n a_i}{n} \right\rfloor \end{align*}

It's not hard to see by global that the statement is true if the floors weren't there(choose any construction and rotate the residues mod $n$ cyclically). The sum of the $b_i$ will then be $\frac{n(n-1)}{2}$ more than a multiple of $n$, so the floor part follows.

Consider choosing $b_i \in \{a_i, a_i + 1, \dots, a_i + (n-1)\}.$ Observe that all possible residues $\pmod{n}$ are encompassed uniquely in the intervals. If we select $(b_1, b_2, \dots, b_n)$ to have residues a permutation of $\{0, 1, \dots, n-1\}$ and assign $b_i$ to the corresponding value in the interval we satisfy conditions $(1), (2).$ The expected value of $b_i - a_i$ is $\frac{n-1}{2}$ since $b_i$ has equal probability of being any residue. Therefore the expected value of $\frac{1}{n}(\sum_{i = 1}^{n} b_i - a_i) = \frac{n-1}{2}$ by LoE. By Pigeonhole Principle, there must exist a tuple $(b_1, b_2, \dots, b_n)$ satisfying, \begin{align*} \frac{1}{n} (\sum_{i = 1}^{n} b_i - a_i) &\le \frac{n-1}{2} \\ \frac{1}{n}(b_1 + b_2 + \cdots+ b_n) &\le (\frac{n-1}{2} + \frac{1}{n}(a_1 + a_2 + \cdots + a_n)). \end{align*}Observe that $\frac{1}{n}\sum_{i = 1}^{n} b_i - \frac{(n-1)}{2} \equiv \frac{1}{n} \frac{n(n-1)}{2} - \frac{n-1}{2} \equiv 0 \pmod{n}$ hence we conclude, $$(b_1 + b_2 + \cdots+ b_n) \le n(\frac{n-1}{2} + \lfloor \frac{a_1 + a_2 + \cdots + a_n}{n} \rfloor).$$

Let us assume $b_i = q_i \cdot n + r_i,$ with $r$ being a permutation of $\{0, 1, \dots, n - 1 \}$, so that $r_1 + r_2 + \dots + r_n = \frac{n(n - 1)}{2}$. Then, we must have $$q_1 + q_2 + \cdots + q_n \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor,$$and also for the second condition, we must have $a_i \le q_i \cdot n + r_i,$ or $\left \lceil \frac{a_i - r_i}{n} \right \rceil \le q_i,$ or $\left \lfloor \frac{a_i - r_i + n - 1}{n} \right \rfloor \le q_i,$ but if $r_i$ is a permutation of $\{0, 1, \dots, n - 1 \}$, $n - 1 - r_i$ is a permutation also, so call this $p$. So, we write this compactly as $q_i \ge \frac{a_i + p_i}{n}$ and our earlier condition doesn't change, just that $r$ is replaced by $p$ so it suffices to show that there exists some permutation $p$ of $\{0, 1, \dots, n - 1\}$ with $$\left \lfloor \frac{a_1 + p_1}{n} \right \rfloor + \left \lfloor \frac{a_2 + p_2}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + p_n}{n} \right \rfloor \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor.$$Now, consider the expected value of above expression over all possible $p$. By LoE, it is just $$\frac{\left \lfloor \frac{a_1}{n} \right \rfloor + \left \lfloor \frac{a_1 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_1 + n - 1}{n} \right \rfloor}{n} + \frac{\left \lfloor \frac{a_2}{n} \right \rfloor + \left \lfloor \frac{a_2 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_2 + n - 1}{n} \right \rfloor}{n} + \dots + \frac{\left \lfloor \frac{a_n}{n} \right \rfloor + \left \lfloor \frac{a_n + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + n - 1}{n} \right \rfloor}{n}.$$But, by Hermite identity, we have $$\left \lfloor \frac{a_i}{n} \right \rfloor + \left \lfloor \frac{a_i + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_i + n - 1}{n} \right \rfloor = a_i,$$for any $i$. So, the expected value is $\frac{a_1 + a_2 + \dots + a_n}{n},$ but since the above quantity can only be an integer, it follows that there exists some such permutation with it not exceeding $\left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor$.

Since subtracting $n$ from $a_i$ and $b_i$ for some $i$ keeps a, b, and c true, we can assume that $0\le a_i < n$ WLOG. For some $i$, let $b_i\mod n = x$. Then, $a_i > x$ with probability $\frac{a_i}{n}$. If $a_i>x$ then $b_i=x$ works, otherwise $b_i=x+n$ works. Notice that $b_1\mod n, b_2\mod n,\dots, b_n\mod n$ is a permutation of $0,1,\dots,n-1$, so $\mathbb{E}[b_1+\dots+b_n]=\frac{n(n-1)}{2}+n\sum_{i=1}^{n}\frac{a_i}{n}=n(\frac{n-1}{2}+\frac{a_1+\dots+a_n}{n})$. Since $b_1+\dots+b_n-\frac{n(n-1)}2$ must be a multiple of $n$, we must have that $b_1+\dots+b_n\le n(\frac{n-1}{2}+\lfloor\frac{a_1+\dots+a_n}{n}\rfloor)$ for some $b_1,\dots,b_n$, as desired.

natural

$ $

Assume the contrary. Assign each $b_i$ with $\pi(i)$ where $\pi$ is a permutation of $\{1,\dots,n\}$; such that $b_i \equiv \pi(i) \pmod n$. And now greedily choose $b_i$ to be the smallest number to satisfy this and the first condition of the question; and call such sequence $(b_1,\dots,b_n)$ \emph{good}. And so for all good sequences we have that the third condition is not satisfied. And so we have \[\sum_i b_i-a_i \geq \frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\}\]This is because the LHS and RHS in the third condition is obviously congruent. So now, we will sum up this expression for all such good sequences. See that for a particular $a_i$, we have that $\sum b_i-a_i$ for different choices of $b_i$ being assigned to $1$, $\dots$ or $n$; it is equal to \[(n+0-a_i+\dots+n+a_i-1-a_i)+(a_i-a_i+\dots+n-1-a_i)=na_i-na_i+\frac{n(n-1)}2=\frac{n(n-1)}2\]And hence the total summation gives us \begin{align*} &\frac{n(n-1)}2 \cdot (n-1)! \cdot n \geq n! \left(\frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\} \right) \iff \left \{\frac{\sum_i a_i}n \right\} \geq 1 \end{align*}Which is a contradiction.

Why so many solutions with randomness??? Childish greedy suffices, probabilistic stuff is too fancy for this problem. For each $i$ pick the smallest possible $b_i \geq a_i$ such that the remainder $b_i \pmod n$ does not appear among those of $b_1,\ldots, b_{i-1}$. Then for $i$ there are at most $i-1$ forbidden remainders mod $n$ from the previous numbers, so $b_i \leq a_i + i - 1$ for all $i$ and the distinct remainders condition is satisfied. Summing yields $\sum_{i=1}^n b_i - \frac{n(n-1)}{2} \leq \sum_{i=1}^n a_i$. The left-hand side is a multiple of $n$ (as the $b_i$ give the remainders $0,1,\ldots,n-1$ each once), so it is at most the largest multiple of $n$ not exceeding the right-hand side, i.e. $n\left\lfloor \frac{\sum_{i=1}^n a_i}{n} \right\rfloor$ and we are done.

Let $b_i-a_i=c_i$ , we know that the maximum of the sum $c_1+c_2+ \dots +c_n = \frac{n(n-1)}{2}$. Hence we have that \begin{align*} b_1+b_2+\dots +b_n &= (a_1+a_2+ \dots+a_n)+ (c_1+c_2+\dots+c_n)\\ &\leq (a_1+a_2+ \dots+a_n)+ \frac{n(n-1)}{2} \end{align*}Now as \[ b_1+b_2+\dots+b_n \equiv \frac{n(n-1)}{2}\pmod{n}\]Then we have that. \[ n |b_1+b_2+\dots+b_n-\frac{n(n-1)}{2}\] Hence it can at most be the largest multiple of $n$ less than or equal to $a_1+a_2+\dots+a_n$. Which means it’s $n\lfloor \frac{a_1+a_2+\dots+ a_n}{n} \rfloor$, hence we are done.

Nice problem! Obviously, we can pick non-negative integers $x_1, x_2, \dots, x_n$ such that the set $\{a_1 + x_1, a_2 + x_2, \dots, a_n + x_n\}$ is a complete residue system modulo $n$. Let $y_i$ be the number of times $i$ appears on the set $\{x_1, x_2, \dots, x_n\}$. (We can make sure that $0 \le x_1, x_2, \dots, x_n \le n - 1$.) Then after adding $k$ on each term of the set $\{x_1, x_2, \dots, x_n\}$ and taking modulo $n$, we see that the sum of our set will become $S_k = \sum_{i=0}^{n-1-k} (i + k)y_i + \sum_{i=n-k}^{n-1} (i + k - n)y_i$, and note that $\sum_{k=0}^{n-1} S_k = \sum_{i=0}^{n-1} y_i(i + (i+1) + \dots + (n-1) + 0 + 1 + \dots + (i-1)) = \frac{n(n-1)}{2}\sum_{i=0}^{n-1} y_i = \frac{n^2(n-1)}{2}$. Therefore, by pigeonhole principle, we can choose $k$ such that the sum of the set $\{x_1 + k, x_2 + k, \dots, x_n + k\} (n)$ is less or equal to $\frac{n(n-1)}{2}$. Let $z_i$ be the remainder of $x_i + k$ upon division by $n$, and let $r$ be the remainder of $a_1 + a_2 + \dots + a_n$ when divided by $n$. Then, since $\{a_1 + z_1, a_2 + z_2, \dots, a_n + z_n\}$ is a complete residue system module $n$, we have $(a_1 + z_1) + (a_2 + z_2) + \dots + (a_n + z_n) \equiv \frac{n(n-1)}{2} (n)$. $\implies z_1 + z_2 + \dots + z_n \equiv \frac{n(n-1)}{2} - r (n)$. Since $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2}$, we get that $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2} - r$. Hence, if we set $b_i = a_i + z_i$, we deduce that $b_1 + b_2 + \dots + b_n = (a_1 + a_2 + \dots + a_n) + (z_1 + z_2 + \dots + z_n) \le \frac{n(n-1)}{2} - r + (a_1 + a_2 + \dots + a_n) = n(\frac{n-1}{2} + \left\lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right\rfloor)$, as desired. $\blacksquare$

wanted greedy, ended up with expected value

No expected value, just some quick and nice observations with residues. Lemma: There exist positive integers $c_1,c_2,...,c_n\in\{0,1,2,...,n-1\}$ such that $a_i+c_i \neq a_j+c_j$(mod $ n$) $\forall i\neq j$ and $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}$. Proof: Obviously, $\{a,a+1,...,a+n-1\}=\{0,1,...,n-1\}$(mod $n$). Now, for each $i=\overline{1,n-1}$ look at $A_i=\{a_i,a_i+1,...,a_i+n-1\}$ and order its elements in ascending order mod $n$. We can create $n!$ sets that contain $n$ elements, one from each $A_i$ such that no 2 elements are on corresponding positions in their respective $A_i$ and $A_j$ sets. For each such set, we can associate the sum of its elements minus $\displaystyle\sum_{i=1}^{n}a_i$: call it $s_i\forall i=\overline{1,n!}$. We get that $\displaystyle\sum_{i=1}^{n!}s_i=n!\cdot\frac{n(n-1)}{2}$ and by PHP, there is $s_i\le\frac{n(n-1)}{2}$. This means that there is a set $C=\{a_j+c_j|c_j\in\{0,...,n-1\}\forall j\overline{1,n-1}\}$ with the desired properties. We carry on with the problem. Let $b_i=a_i+c_i$. The first $2$ conditions clearly hold, so all that remains is to show that the third one is true as well. Let $\displaystyle\sum_{i=1}^{n}a_i=cn+r$, with $r\le n-1$. Obviously, $\displaystyle\sum_{i=1}^{n}(a_i+c_i)=\frac{n(n-1)}{2}$ (mod $n$), so $\displaystyle\sum_{i=1}^{n}c_i=\frac{n(n-1)}{2}-r$ (mod $n$), meaning that $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}-r$(assuming the contrary quickly leads to a contradiction). We now wish to prove that $\displaystyle\sum_{i=1}^{n}(a_i+c_i)\le \frac{n(n-1)}{2}+\bigg\lfloor\frac{\displaystyle\sum_{i=1}^{n}a_i}{n}\bigg\rfloor$. Since the $LHS\le nc+r+\frac{n(n-1)}{2}-r=RHS$ we are done.