Можно ли обойти доску, изображенную на рисунке, побывав на каждой клетке ровно один раз? (Двигаться можно только на соседнюю по стороне клетку, начало и конец пути могут быть где угодно).
Занумеруем поля доски (рис. слева) и нарисуем граф (рис. в центре), где вершины соответствуют полям, а ребро проводится, если соответствующие поля отстоят на ход коня. На графе легко построить требуемый обход (жирная линия). На рис. справа поля занумерованы уже в порядке обхода.
Ответ
Можно.
Замечания
Приведённый маршрут обхода, конечно, не единственный.
Answers & Comments
Ответ:
Занумеруем поля доски (рис. слева) и нарисуем граф (рис. в центре), где вершины соответствуют полям, а ребро проводится, если соответствующие поля отстоят на ход коня. На графе легко построить требуемый обход (жирная линия). На рис. справа поля занумерованы уже в порядке обхода.
Ответ
Можно.
Замечания
Приведённый маршрут обхода, конечно, не единственный.