Разбиение доски на части

Давайте обозначим Для решения достаточно показать, что (1) Гриша всегда сможет набрать сумму больше и (2) Яша может расставить числа так, чтобы Гриша не смог набрать сумму больше

(1) Раскрасим клетки в черный и белый цвет в шахматном порядке. Сумма всех чисел нечетна, поэтому сумма чисел в клетках какого-то цвета будет больше — тогда Грише достаточно выбрать все клетки этого цвета.

(2) Разобьем доску на квадрат и каёмку толщиной в клетку. Далее разобьем квадрат на квадраты а каёмку — на прямоугольники один прямоугольник и один прямоугольник Разобьем множество на подмножества: и четверки и т. д.,

В каждый квадрат мы поставим четверку чисел чтобы и стояли на одной диагонали, а и — на другой; тогда в любом случае Гриша из клеток этого квадрата наберет не более полусуммы чисел в этом квадрате.

В каждый прямоугольник мы поставим четверку чисел в порядке (в средние клетки тогда Гриша из клеток этого прямоугольника наберет не более то есть не более полусуммы чисел в этом прямоугольнике.

В прямоугольник поставим тройку ( в середине); тогда Гриша из клеток этого прямоугольника наберет не более то есть не более полусуммы чисел в этом прямоугольнике.

Наконец, в прямоугольник поставим числа и Суммируя по всем прямоугольникам разбиения, видим, что общая сумма Гриши не прeвысит

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 1. Для решения можно использовать другие разбиения, кроме перечисленных в решении фигур , в них могут участвовать уголки из трех клеток. Соответственно, множество всех чисел может быть разбито на четверки вида и тройки вида .

Замечание 2. В аналогичной задаче для любых достаточно больших размеров таблицы ответом будет , округленное вверх.