Задача
COM-B1-M07-P016 Замкнутый путь коня
#16
★★★☆☆ Уровень 3 из 5
Докажите, что на доске \(5\times5\) не существует замкнутого пути коня, проходящего через каждую клетку ровно один раз.
Замкнутый путь коня был бы циклом нечетной длины в двудольном графе.
Покрасим доску шахматно. Каждый ход коня меняет цвет, значит граф ходов коня двудольный: все ребра идут между двумя цветами. Замкнутый путь, проходящий через \(25\) клеток, был бы циклом длины \(25\). Но в двудольном графе все циклы имеют четную длину, потому что цвета чередуются. Противоречие.
Мостик к модулю о графах.