Задача
Пусть A – угловая клетка шахматной доски, B – соседняя с ней по диагонали клетка. Докажите, что число способов обойти всю доску хромой ладьей (ходит на одну клетку по вертикали или горизонтали), начиная с клетки A, больше, чем число способов обойти всю доску хромой ладьей, начиная с клетки B. (Ладья должна побывать на каждой клетке ровно один раз.)
Решение
Каждому пути Г, (обходящему всю доску и) начинающемуся с B, поставим в соответствие путь, начинающийся с A. Для этого по части Г, соединяющей B с A, пройдём в обратном направлении, а затем (заменив ход из A ходом из B) продолжим его по оставшейся части (если она есть). Это возможно, поскольку каждая клетка, соседняя с A, является соседней и с B. При этом разные пути, очевидно, превращаются в разные.
Осталось предъявить маршрут, начинающийся с A, который нельзя получить таким способом. Таковым является любой обход, когда ладья попадает в B после того, как прошла по обоим соседям A. Например, годится обход доски по "скручивающейся" спирали.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь