Задачки

Условие

В таблице 8*8 записаны все целые числа от 1 до 64 по одному разу. Докажите, что найдутся два соседних числа, разность между которыми не меньше 5. Клетки считаются соседними, если они имеют общую сторону.

Подсказка

Пройдите от клетки, в которой записана единица, до клетки, в которой записано число 64, сдвигаясь на одну клетку по горизонтали или по вертикали.

Решение

Назовем длиной пути между двумя клетками таблицы минимальное число ходов на одну клетку по горизонтали или по вертикали, необходимое для того, чтобы попасть с одной из этих клеток на другую. Нетрудно видеть, что длина пути между некоторыми двумя клетками таблицы не превосходит 14 (максимальная длина пути - между двумя клетками, расположенными в противоположных углах). Пройдем от клетки, в которой записана единица, до клетки, в которой записано число 64, по кратчайшему пути, сдвигаясь на одну клетку по горизонтали или по вертикали. При этом мы сделаем не более 14 сдвигов (число сдвигов не больше максимально возможной длины пути). Предположим, что условие задачи не выполнено. Тогда число, записанное в клетке, после одного сдвига увеличится не более, чем на 4. После 14 сдвигов число увеличится не больше, чем на 4*14 = 56. Таким образом, получим, что 64 не больше, чем 1 + 56 = 57. Это противоречие завершает решение задачи.

МЦНМО