Задача
COM-B2-M05-P005 Выравнивание двух куч
#5
★★☆☆☆ Уровень 2 из 5
В двух кучах \(a\) и \(b\) камней, причём \(a\ge b+2\). За ход один камень перекладывают из большей кучи в меньшую. Докажите, что сумма квадратов размеров куч уменьшается.
Сравните \(a^2+b^2\) и \((a-1)^2+(b+1)^2\).
После хода размеры куч станут \(a-1\) и \(b+1\). Разность старой и новой сумм квадратов равна
\[a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1).\]
Так как \(a\ge b+2\), правая часть положительна. Значит, сумма квадратов строго уменьшается.
Этот расчёт затем используется в задачах о завершении процессов.