EGMO

Sea $n \geq 2$ un número entero, y sean $a_1, a_2, \dots , a_n$ enteros positivos. Muestre que existen enteros positivos $b_1, b_2, \dots , b_n$ que cumplen las siguientes tres condiciones: $a_i \le b_i$ para todo $i = 1, 2, \dots , n$; los residuos de $b_1, b_2, \dots , b_n$ al dividirlos entre $n$ son todos diferentes; y \[b_1+b_2+\cdots b_n \le n\left(\frac{n-1}{2}+\left\lfloor \frac{a_1+a_2+\cdots a_n}{n}\right \rfloor \right)\] Nota: Denotamos por $\lfloor x\rfloor$ a la parte entera del número real $x$, es decir, al mayor entero que es menor o igual a $x$.