Problem
COM-B2-M05-P012 Stones Move to the Right
#12
★★★☆☆ Level 3 of 5
Several stones lie on a strip of \(n\) cells. In one move, one stone may be moved one cell to the right if it is not in the \(n\)-th cell. Prove that an infinite sequence of moves is impossible.
Consider the sum of the indices of the cells containing stones.
Let \(S\) be the sum of the indices of the cells containing stones, counting stones with multiplicity. Each move increases \(S\) by exactly \(1\).
If there are \(m\) stones, then \(S\le mn\), because no stone can go beyond the \(n\)-th cell. Thus \(S\) strictly increases but is bounded above. Infinitely many moves are impossible.
A simple but very important template for termination problems.