Вырезаем прямоугольник, задача для 6-го класса

[gipokrat]

В 2014 году в рамках занятия математического кружка шестиклассникам предлагалась следующая задача.

Цитата:

Из квадрата на рисунке можно вырезать прямоугольник, сумма чисел в котором равна $n$ для любого $n$ от $1$ до $8$, а с суммой $9$ — нельзя. Расставьте натуральные числа в квадрате $3\times3$ так, чтобы можно было вырезать прямоугольники с любой суммой от $1$ до $N$ для как можно большего $N$.

Для определённости: под прямоугольником здесь понимается прямоугольник, составленный из целых клеток таблицы $3\times3$, со сторонами, параллельными сторонам квадрата.

Пример из условия:

$$ \begin{matrix} 1&1&5\\ 1&1&1\\ 1&1&1 \end{matrix} $$

В нём действительно можно получить все суммы от $1$ до $8$, но нельзя получить сумму $9$.

У меня получается следующий пример, дающий уже $N=29$:

$$ \begin{matrix} 9&15&2\\ 1&4&6\\ 13&3&12 \end{matrix} $$

Если обозначить клетки так:

$$ \begin{matrix} a&b&c\\ d&e&f\\ g&h&i \end{matrix}, $$

то для этой таблицы суммы от $1$ до $29$ получаются следующим образом:

$$ \begin{array}{c|l} 1&d\\ 2&c\\ 3&h\\ 4&e\\ 5&d+e\\ 6&f\\ 7&e+h\\ 8&c+f\\ 9&a\\ 10&a+d\\ 11&d+e+f\\ 12&i\\ 13&g\\ 14&d+g\\ 15&b\\ 16&g+h\\ 17&b+c\\ 18&f+i\\ 19&b+e\\ 20&c+f+i\\ 21&d+e+g+h\\ 22&b+e+h\\ 23&a+d+g\\ 24&a+b\\ 25&e+f+h+i\\ 26&a+b+c\\ 27&b+c+e+f\\ 28&g+h+i\\ 29&a+b+d+e \end{array} $$

Вопрос: является ли $29$ максимальным возможным значением $N$? Если да, хотелось бы увидеть доказательство, желательно без полного перебора. Если нет — интересен пример с большим $N$.

[Null]

почти наверняка проблема в количестве четных/нечетных чисел, но надо перебирать $2^9$ вариантов

[gipokrat]

Null в сообщении #1724251 писал(а):

почти наверняка проблема в количестве четных/нечетных чисел, но надо перебирать $2^9$ вариантов

Да, спасибо, это действительно естественный первый фильтр.

Если возможно $N=30$, то число прямоугольников нечётной суммы должно быть от $15$ до $21$ включительно: среди чисел $1,\ldots,30$ ровно $15$ нечётных и $15$ чётных, а всего прямоугольников $36$.

Я проверил этот перебор по всем $2^9$ паритетным шаблонам. Число $k$ прямоугольников нечётной суммы получается таким:

$$ \begin{array}{c|cccccccc} k&0&9&12&16&17&20&21&24\\ \hline \#&1&16&24&81&144&144&96&6 \end{array} $$

Так что по одному только количеству чётных/нечётных прямоугольников случай $N=30$ не отсекается: остаются шаблоны с $k=16,17,20,21$.

[tolstopuz]

Кстати, полный перебор (для чисел в клетках, ограниченных $18$) показал, что решение с $N=29$ максимально и единственно с точностью до поворотов и отражений.