Задача
Доска 2$N$×2$N$ покрыта неперекрывающимися доминошками 1×2. По доске прошлахромаяладья, побывав на каждой клетке по одному разу (каждый ход хромой ладьи – на клетку, соседнюю по стороне). Назовём ходпродольным, если это переход из одной клетки доминошки на другую клетку той же доминошки. Каково а) наибольшее;
б) наименьшее возможное число продольных ходов?
Решение
а)Оценка.Количество продольных ходов не превосходит количества 2$N$² доминошек (так как в каждой доминошке не более одного продольного хода).Пример. Возьмём любой обход ладьей и занумеруем клетки в порядке обхода. Пусть клетки 2$k$ – 1 и 2$k$ образуют доминошку для всех $k$ от 1 до 2$N$². Тогда число продольных ходов равно числу доминошек.
б) Случай $N$ = 1 очевиден. Пусть $N$ > 1. Оценка. При проходе угла один из двух ходов будет продольным. Один угол может быть началом пути ладьи, другой – концом, а оставшиеся углы придётся проходить. Поэтому будет хотя бы два продольных хода.
Пример. Положим в верхние углы доски по вертикальной доминошке, а все остальные положим горизонтально. Пусть ладья идёт змейкой из левого нижнего угла (см. рисунок). Продольными будут лишь два хода – в вертикальных доминошках.
Ответ
а) 2$N$² ходов. б) 1 ход при $N$ = 1; 2 хода при $N$ > 1.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь