Подсчеты в клетчатых задачах

Пример. На картинке показано, в каком порядке красить клетки: сначала красим все серые клетки, дальше в порядке возрастания номеров. Несложно видеть, что у каждой клетки с номером, начиная с не более одного соседа с бoльшим номером.

Оценка. Предположим, что клеток с числами, большими не более Тогда в них написаны числа, не превосходящие Заметим, что в последней закрашенной клетке написано число В остальных клетках написано число, не превосходящее Таким образом, сумма всех чисел не больше С другой стороны, сумма всех чисел равна количеству пар соседних чисел в таблице, то есть