Problem: Starting with $35$ integers you may select $23$ of them and add $1$ to each. By repeating this step, one can make all $35$ integers equal. Prove this.
My Attempt: I know that we have to find an invariant. And I think that the sum of the integers $S\equiv 0\pmod{23}$ but this does not give much information. Any hints will be much appreciated.
Start with 35 empty spots. Take $3 \times 23$ beans, in groups of 23.
Take the first group of 23 beans and put a bean in the first 23 slots.
Then with the next group of 23, put a bean in the next 12 empty spots, and the remaining 11 into the first 11 spots.
With the last group of 23, put a bean in spots 12 through 34.
(another way to describe this is "deal the 69 beans into the 35 slots, as if you were dealing cards to 35 players in a card game; the first 34 players get 2 cards, the 35th player gets only one."
The end result: 34 piles of 2 beans, and 1 pile with only 1 bean.
Now if you added these to your particular cluster of numbers (again represented as 35 piles of (different numbers of) beans, arranging for the "one bean short" pile to fall on your largest starting number, almost all piles would grow equally, but the fullest pile would grow by one less. So the difference between the fullest pile and the least-full would decrease (at least if there's only one "fullest" pile).
Repeat, "subtracting" a bean from each overfull pile in this method until all piles have the same number of beans.
Let $35$ be $m$ and $23$ be $n$. We can now generalise the problem.
Suppose $\gcd(m, n) = 1$. We know form the Bezout Identity $nx -my=1$ has a solution with $x$ and $y$ from $\{1, 2, \dots, m - 1\}$. We rewrite this equation in the form $nx=my+1$.
Now we place our $m$ positive integers $a_1\leq a_2 \leq \dots \leq a_m$ in a circle and proceed as follows: go around the circle, starting from $a_1$ and in blocks of $n$, and increase each number in a block by $1$. After you've done this $x$ times, you've performed a total of $nx=my+1$ increments. In other words, you've gone around the circle $y$ times, and through the first number $a_1$ one additional time. This means $a_1$ is increased by one more than the others, and in this way the difference $\max_i a_i - \min_j a_j$ decreases by one.
One may repeat this each time placing a minimal element in the beginning, until the difference between the maximal and minimal element is reduced to zero.
But if $\gcd(m, n) = d > 1$, then such a reduction is not always possible. Let one of the $m$ numbers be $2$ and all the others be $1$. Suppose that applying the same operation $k$ times we get equidistribution of the $(m + kn+1)$ units to the $m$ numbers. This means $m + kn +1 \equiv 0 \pmod m$. But $d$ doesn’t divide $m + kn + 1 $ since $d > 1$. Hence $m$ doesn’t divide $m + kn+1$. This is a contradiction!
If you pick 23 of the smallest numbers and add 1 to all of them; repeating that. Eventually you will have $x$ numbers equal to $n$ and $35 - x$ numbers equal to $n-1$.
On the next iteration, you will have $x - 23 \pmod {35}$ integers equal to some $n$ and the rest equal to $n+1$. The next step will have $x - 23 \times 2 \pmod {35}$ equal to some $n$ and the reset equal to $n+1$. Can you see what happens if you keep repeating this? Can you prove that eventually $x=0$ ?
