Problem
COM-B2-M05-P016 Piles Become Almost Equal
Several piles contain stones. If one pile has at least \(2\) more stones than another, one may move one stone from the larger pile to the smaller pile. Prove that the process must terminate, and at the end any two pile sizes differ by at most \(1\).
The sum of squares of pile sizes strictly decreases.
Consider the sum of squares of all pile sizes. If a stone is moved from a pile of size \(a\) to a pile of size \(b\), where \(a\ge b+2\), then the contribution of these two piles changes from \(a^2+b^2\) to \((a-1)^2+(b+1)^2\). As computed, the old sum exceeds the new one by \(2(a-b-1)>0\).
The sum of squares is a nonnegative integer, so it cannot strictly decrease forever. The process terminates.
If in the final state two piles differed by at least \(2\), a move would still be allowed. Hence in the end any two pile sizes differ by at most \(1\).
The idea is inspired by pile-process problems, but this is an independent training version.