Целые числа на шахматной доске

[Ktina]

В каждое из полей шахматной доски вписали по целому числу, причём оказалось, что числа, вписанные в поля с общей стороной, отличаются либо на 1, либо на 2. Какое наибольшее количество попарно различных чисел могло быть вписано?
Обобщите задачу на квадратную доску произвольного размера, а также на прямоугольную доску произвольноых размеров.

[ИСН]

Каждый квадратик $2\times2$ представляет собой картинку либо $\begin{array}{c|c}0&1\\\hline1&2\end{array}+\rm const$, либо $\begin{array}{c|c}0&1\\\hline1&0\end{array}+\rm const$. Первое - это наклонная плоскость по диагонали доски, а второе - перегиб на ней. Перегибы нам явно не добавят значений, значит, их и не надо.

[zhekas]

ИСН в сообщении #1254429 писал(а):

Каждый квадратик $2\times2$ представляет собой картинку либо $\begin{array}{c|c}0&1\\\hline1&2\end{array}+\rm const$, либо $\begin{array}{c|c}0&1\\\hline1&0\end{array}+\rm const$.

А почему не $\begin{array}{c|c}0&1\\\hline2&3\end{array}+\rm const$ например?

[ИСН]

А, там по стороне... Тьфу, чёрт, тогда вещи становятся волосатыми.

[worm2]

Без ограничения общности можно считать, что минимальное число — 0.
Также без ограничения общности можно считать, что остальные числа — кусок натурального ряда, без разрывов. А почему? А потому что если у нас есть разрыв, то числа разбиваются на 2 части: меньшие разрывного, и большие. Уменьшив большие на величину разрыва, мы сохраним число различных чисел, и не увеличим разницу между соседними числами.
Будем понимать под шагом переход на соседнюю клетку по горизонтали или вертикали, а под путём — последовательность шагов.
На обычной доске 8x8 между любыми клетками существует путь длиной не более 14. Значит, максимальное значение может быть не больше 28.
Пусть в какой-то клетке записано 28. Очевидно, она должна находиться в одном из углов, а в противоположном должен быть нуль. Поразмыслив ещё немного, приходим к выводу, что, в силу экстремальности числа 28, вся расстановка однозначно определяется, и у нас получилось разместить всего 15 чисел (чётных). Красиво, но мало.
Попробуем-ка мы разместить 28 различных чисел от 0 до 27.
Пробуем... пробуем.... а не получается.
А почему?
Ну давайте предположим, что это у нас руки кривые, а так-то должно было получиться. Понятно, что 0 и 27 по-прежнему в противоположных углах. Протянем между ними диагональ. Числа на диагонали, в силу околоэкстремальности числа 27, имеют весьма мало пространства для манёвра. А именно, между соседними клетками этой диагонали одна разность чисел равна 3, а остальные шесть равны 4 (иначе одна из разностей была бы больше 4, что, очевидно, невозможно). Нас интересует та пара смежных клеток диагонали, числа в которых отличаются на 3. Через общую точку этой пары клеток проведём горизонтальную и вертикальную прямые, которые делят доску на 4 части: два квадрата (в одном из которых 0, в противоположном 27) и два прямоугольника.
Числа внутри квадратов определяются однозначно. Это ключевое утверждение, без хорошего понимания которого в дальнейших рассуждениях невозможно разобраться.
В "нулевом" квадрате — только чётные числа, в противоположном — только нечётные. Где-то в двух оставшихся прямоугольниках мы должны разместить числа 1 и 26 (которых внутри квадратов нет). А не получится! Потому что 1 должен быть недалеко от нуля, но тогда "нулевой" квадрат должен быть размерами не более 2x2, но тогда противоположный квадрат — размерами не менее 6x6, и вне него мы не можем разместить 26, т.к. легко посчитать, что максимальное число вдоль той границы квадрата, рядом с которой мы можем размещать числа — не более 17.

Итак, больше 27 различных чисел мы разместить не сможем. А 27 — запросто. Это совсем не сложно, но что-то мне лень таблицу рисовать... Например, так: в одном углу квадрат 2x2 (сверху строка (0, 2), снизу строка (1, 3)), в противоположном — квадрат ((23, 24), (25, 26)), на диагонали между 3 и 23 внутренний квадрат 6x6 определяется однозначно, он заполнен регулярным образом нечётными числами. Остаются незадействованными чётные от 4 до 22, которые легко размещаются на оставшихся полосках: горизонтальной 4..12, в углу 13, и вертикальной 14..22. Божечки, как же ж мне лень таблицу рисовать... Там ещё нужно показать, что в оставшихся полосках числа размещаются без проблем.

[Ktina]

worm2
Большое спасибо!