Решение задачи 245

Условие:

На полях шахматной доски расставлены целые числа, причем никакое число не встречается дважды. Докажите, что есть пара соседних (по стороне) клеток, числа в которых отличаются не меньше, чем на 5.

Решение:

Рассмотрим наибольшее и наименьшее числа. Из условия следует, что они отличаются хотя бы на 63. Проведем путь от наименьшего числа к наибольшему минимальной длины. Тогда в этом пути не более 14 переходов между соседними клетками (не более семи по горизонтали и не более семи по вертикали). Предположим, что в этом пути все соседние числа отличаются не более, чем на 4. Но тогда наибольшее число отличается от наименьшего не более чем на 14*4=56, противоречие. Значит в этом пути есть хотя бы одна пара соседних чисел, отличающихся не менее, чем на 5.