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