Bogdanov I.I.

2009 non-negative integers not exceeding 100 are arranged in a circle. It is allowed to add 1 to two adjacent numbers, and this operation can be performed with any two adjacent numbers no more than $k$ times. For what least $k$ can all the numbers be guaranteed to be made equal?
Let the numbers on the circle be denoted by $a_{1}, \ldots, a_{2009}$, and set $a_{n+2009} = a_{n} = a_{n-2009}$. Let $N = 100400$.

1. Set $a_{2} = a_{4} = \ldots = a_{2008} = 100$ and $a_{1} = a_{3} = \ldots = a_{2009} = 0$. Suppose we managed to make all the numbers equal for some value of $k$. Consider the sum $S = (a_{2} - a_{3}) + (a_{4} - a_{5}) + \ldots + (a_{2008} - a_{2009})$. This sum increases by 1 when 1 is added to the pair $(a_{1}, a_{2})$, decreases by 1 when added to the pair $(a_{2009}, a_{1})$, and does not change with all other operations. Since the initial value of $S$ is $S_{0} = 100 \cdot 1004 = N$, and the final value should be zero, the pair $(a_{2009}, a_{1})$ must have been increased at least $N$ times. This means that $k \geq N$.
2. It remains to show that for $k = N$, the required result is always possible. Consider an arbitrary set of numbers $a_{i}$. Increase each pair $(a_{i}, a_{i+1})$ exactly $s_{i} = a_{i+2} + a_{i+4} + \ldots + a_{i+2008}$ times. Then the number $a_{i}$ will become

$$
a_{i} + (a_{i+2} + a_{i+4} + \ldots + a_{i+2008}) = a_{1} + \ldots + a_{2009}
$$

that is, all numbers will become equal. On the other hand, $s_{i} \leq 1004 \cdot 100 = N$, which is what we needed to show.