|
|
 |
Условие
В таблицу 9×9 вписаны все целые числа от 1 до 81. Доказать, что найдутся два соседних числа, разность между которыми не меньше 6.
Решение
Где-то в таблице стоит 1, а где-то 81. Соединим эти числа цепочкой, переходя от одного числа к другому (стоящему в соседней клетке), сделав минимальное число переходов (их будет не более 16). Если в таблице разность между соседними меньше 6, то число переходов в цепочке ровно 16, иначе нашелся бы переход с разностью, большей 5. Значит, 1 и 81 стоят в противоположных углах таблицы, а в цепочке стоят числа 1, 6, 11, 16, 21, ..., 81. Рассмотрим другую минимальную цепочку, соединяющую 1 и 81. В ней тоже должны стоять числа 1, 6, 11, 16,..., 81. Но в таблице все числа различны. Противоречие.
Замечания
1. Ср. с задачами 78494, 98071.
2. Аналогичная задача для таблицы n×n обсуждается в статье М. Гервера "Задача о числах в таблице".
