|
|
 |
Условие
С четырёх сторон шахматной доски размером n×n построена кайма шириной в два поля. Докажите, что кайму можно обойти шахматным конём, побывав на каждом поле один и только один раз, в тех и только тех случаях, когда n – 1 кратно 4.
Решение
Докажем, что кайму ширины 2 при n = 4k + 1 можно обойти конем.
На рис. 1 показано, как обойти кайму при k = 0 (n = 1).
Лемма. Если в множестве G, состоящем из g полейбесконечной шахматной доски, можно выделить p попарно не пересекающихся подмножеств A1, A2, ..., Ak, которые содержат m полей, причём
а) ни с одного поля подмножества Ai конь не может пройти ни на одно поле подмножества Aj при i ≠ j;
б) g – m < p – 1, то область G нельзя обойти ходом коня.
Доказательство. Если конём удастся обойти всё множество G, то путь коня должен пройти через все p подмножеств. При этом в силу условия а) при переходе из подмножества в подмножество коню придется не менее чем p – 1 раз побывать нейтральных полях (не входящих ни в одно из подмножеств). Но таких полей по условию б) меньше p – 1 .
Теперь докажем, что при n ≠ 4k + 1 кайму обойти нельзя. Рассмотрим три случая.
1) n = 4k + 3. При k = 0 разделим всю кайму на два подмножества A1 и A2 так, как показано на рис. 4.
Для того, чтобы получить рисунок при других k, нужно вставлять блоки, изображённые на рис. 2.
2) n = 4k. При k > 0 нейтральными объявим поля, имеющие по одной общей стороне с угловыми полями окаймляемой доски (на рис. 5 они помечены буквой Z). Их будет 8. Подмножества – их будет 10 – определяются следующим образом: берём незанятое поле и все те поля, в которые можно "пройти" из него конём, не пользуясь нейтральными клетками. Для того, чтобы из рис. 5, где k = 1, получить рисунок при любом k > 0, нужно вставлять блоки, изображённые на рис. 2.
3) n = 4k + 2. Этот случай разбирается аналогично. Здесь при k > 0 число нейтральных полей 12, а число подмножеств 14. Как выбирать нейтральные поля при k > 0 и при k = 0, видно из рис. 7 и 8.
