Задача
COM-B2-M05-P009 Ход коня и цвета
#9
★★★☆☆ Уровень 3 из 5
Конь должен пройти по всем клеткам доски \(5\times5\), посетив каждую клетку ровно один раз. Докажите, что такой путь не может быть замкнутым, то есть последний ход не может возвращать коня в начальную клетку.
Конь при каждом ходе меняет цвет клетки.
Раскрасим доску в шахматном порядке. Каждый ход коня переводит его на клетку противоположного цвета.
Если путь по всем \(25\) клеткам был бы замкнутым, то он образовал бы цикл нечётной длины \(25\), в котором цвета должны строго чередоваться. Но в замкнутом цикле с чередованием цветов длина должна быть чётной. Противоречие.
Задача полезна тем, что цветовой инвариант применяется к графу ходов.