|
|
 |
Условие
Наиль расставляет в клетках квадрата 6×6 числа от 1 до 36 (по одному числу в каждую клетку, числа не повторяются). После этого Наиль ставит фишку в клетку с числом 1. Далее перед каждым ходом Наиль выбирает наибольшее из чисел, стоящих в соседних с фишкой (по стороне или углу) клетках. Если выбранное число больше, чем в клетке с фишкой, то Наиль передвигает фишку в клетку с выбранным числом; иначе фишка больше не двигается.а) Приведите пример расстановки чисел, при которой фишка посетит как можно больше клеток.
б) Докажите, что ни при какой другой расстановке чисел не получится посетить больше клеток.
Решение
а) Расстановка чисел, при которой путь фишки пройдёт по 18 клеткам, приведён на рисунке.б) Заметим, что в каждом квадрате $2\times 2$ фишка может посетить не больше двух клеток. Действительно, пусть в каком-то квадрате $2\times 2$ фишка сначала посетила число $A$, потом через некоторое время – число $B$, большее $A$, а потом – число $C$, большее $B$. Но клетка с $C$ – соседняя с клеткой с $A$, поэтому, находясь в клетке с $A$, фишка должна была шагнуть в клетку с числом $C$ (или с большим числом), и посетить клетку с числом $B$ она бы не могла. Противоречие.
Разделив квадрат $6\times 6$ на 9 квадратиков $2\times 2$, получаем, что в каждом из них посещено не более двух клеток, поэтому суммарно фишка посетит не более 18 клеток.
