Задача
COM-B2-M05-P012 Камни двигаются вправо
#12
★★★☆☆ Уровень 3 из 5
На полоске из \(n\) клеток лежит несколько камней. За ход один камень можно передвинуть на одну клетку вправо, если он не стоит в \(n\)-й клетке. Докажите, что бесконечная последовательность ходов невозможна.
Рассмотрите сумму номеров клеток, где лежат камни.
Пусть \(S\) — сумма номеров клеток, в которых лежат камни, считая камни с кратностью. Каждый ход увеличивает \(S\) ровно на \(1\).
Если всего камней \(m\), то \(S\le mn\), потому что ни один камень не может оказаться правее \(n\)-й клетки. Значит, \(S\) строго возрастает, но ограничена сверху. Бесконечно много ходов невозможно.
Простой, но очень важный шаблон для задач о завершении.