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

Переставив, если нужно, столбцы, будем далее считать, что числа в первой строке стоят в неубывающем порядке. Пусть — ое число первой строки. Рассмотрим сумму

Докажем, что Пусть е слагаемое этой суммы равно Если в этой сумме нет отрицательных членов, все очевидно. Ясно, что то есть Пусть то есть Тогда в первых столбцах содержатся только числа от до следовательно, там содержатся все такие числа. Отсюда следует, что и Таким образом, для любого отрицательного сумма его со следующим членом положительна, поэтому, объединив такие слагаемые в пары, получаем сумму неотрицательных слагаемых. Итак,

Это число достигается для таблицы, в которой первые три клетки первой строки заполнены единицами, а дальше идут числа Далее заполняем столбцы: в первом столбце все единицы, кроме последних двух ячеек, заполненных двойками. Во втором столбце после первой единицы стоят двойки во всех ячейках, кроме последних двух, заполненных тройками. После этого все столбцы, кроме последнего, заполняются по принципу: пусть в первой ячейке этого столбца стоит тогда во всех остальных ячейках, кроме двух последних ставится а в двух последних — В последнем столбце 8 последних ячеек заполняются числом