EGMO 2019
問題 5

$i=1,2,\dots,n$ に対して $a_i$ を $n$ で割った商を $q_i$，余りを $r_i$ とする．$r_1\leq r_2\leq\cdots\leq r_n$ としてもよい．このとき $\max\{r_i-i\}=M$ とすれば $r_k-k=M$ なる整数 $1\leq k\leq n-M$ が取れる．このとき，

$$\sum_{i=1}^nr_i=\sum_{i=1}^{k-1}r_i+\sum_{i=k}^nr_i\geq 0\cdot(k-1)+(M+k)(n-k)=k(n-M-k)+nM\geq nM$$

が成り立つ．また，$b_i=nq_i+M+i$ とすれば

$$b_i\geq nq_i+(r_i-i)+i=a_i$$

より条件 $(\text{A})$ は満たされ，条件 $(\text{B})$ も満たされる．また，先の不等式より

$$n\left(\dfrac{n-1}{2}+\left\lfloor\dfrac{1}{n}\sum_{i}a_i\right\rfloor\right)\geq \dfrac{n(n-1)}{2}+n\left(M+\sum_{i}q_i\right)\geq \sum_i(nq_i+M+i)=\sum_{i}b_i$$

が成り立ち，条件 $(\text{C})$ も満たされる．よって $3$ 条件を満たす $b_1,b_2,\dots,b_n$ が存在する．