Условие
Можно ли доску размерами 4 × N обойти ходом коня, побывав на каждом поле ровно один раз, и вернуться на исходное поле?
Решение
Раскрасим доску 4 × N в 4 цвета так, чтобы, если конь стоит на поле цвета 1 (соответственно 2), то следующим ходом он встанет на поле цвета 3 (соответственно 4).
Тогда так как полей цветов 1 и 2 столько же, сколько и полей цветов 3 и 4, то в случае наличия обхода конем доски цвета пар (1, 2) и (3, 4) чередуются. Следовательно, всякий раз, как конь встает на поле цвета 3, следующим ходом он должен встать на поле цвета 1 или 2 - а легко видеть, что он может встать только на поле цвета 1. Значит, при обходе доски цвета 1 и 3 чередуются. Но это невозможно, так как тогда конь никогда не встанет на поля цветов 2 и 4. Мы пришли к противоречию.
| |
1 |
2 |
1 |
2 |
1 |
2 |
|
| |
3 |
4 |
3 |
4 |
3 |
4 |
|
| |
4 |
3 |
4 |
3 |
4 |
3 |
|
| |
2 |
1 |
2 |
1 |
2 |
1 |
|
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Генкин С.А., Итенберг И.В., Фомин Д.В. |
|
Год издания |
1994 |
|
Название |
Ленинградские математические кружки |
|
Издательство |
Киров: "АСА" |
|
Издание |
1 |
|
глава |
|
Номер |
12 |
|
Название |
Инвариант |
|
Тема |
Инварианты |
|
задача |
|
Номер |
015 |
