Задача
COM-B2-M05-P016 Кучи почти выровнялись
В нескольких кучах лежат камни. Если в одной куче хотя бы на \(2\) камня больше, чем в другой, разрешается переложить один камень из большей кучи в меньшую. Докажите, что процесс обязательно закончится, и в конце размеры любых двух куч отличаются не более чем на \(1\).
Сумма квадратов размеров куч строго уменьшается.
Рассмотрим сумму квадратов размеров всех куч. Если камень перекладывается из кучи размера \(a\) в кучу размера \(b\), где \(a\ge b+2\), то вклад этих двух куч меняется с \(a^2+b^2\) на \((a-1)^2+(b+1)^2\). Как было вычислено, старая сумма больше новой на \(2(a-b-1)>0\).
Сумма квадратов — неотрицательное целое число, поэтому она не может строго убывать бесконечно. Процесс закончится.
Если в конечном состоянии две кучи отличались бы хотя бы на \(2\), ход всё ещё был бы разрешён. Значит, в конце любые две кучи отличаются не более чем на \(1\).
Идея вдохновлена задачами о процессах с кучами, но здесь дана самостоятельная тренировочная версия.