Клетчатые задачи и комбинаторные подсчёты на СПБГУ

Поскольку сумма чисел в прямоугольнике нечетна, если ее модуль больше трех, то он хотя бы пять. Предположим, что такая расстановка нашлась. Заметим, что в ней либо нет ни одной строки, состоящей из одних либо нет ни одного столбца, состоящего из одних (если есть и такая строка, и такой столбец, то в их общей клетке с одной стороны должна стоять с другой Разберем первый случай (второй разбирается аналогично). Рассмотрим прямоугольник расположенный в левом верхнем углу. Модуль суммы чисел в нем хотя бы Сдвинем этот прямоугольник на одну клетку вправо. В нем модуль суммы чисел также хотя бы Поскольку по сравнению с первым прямоугольником у него одна тройка чисел заменена на другую, суммы чисел в прямоугольниках отличаются не более, чем на Но тогда они должны быть одного знака, ибо и отличаются больше, чем на Сдвинем прямоугольник еще на одну клетку вправо и снова получим, что сумма чисел в нем того же знака, что и в предыдущем, и т. д.. Таким образом, мы установим, что все суммы чисел в сдвинутых вправо прямоугольниках одного знака. Тогда модуль суммы чисел в трех верхних строках не меньше, чем поскольку эти строки разбиваются на таких прямоугольников. Аналогичный вывод можно сделать про любые три соседние строки.

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