Условие
Участок m×n. Прямоугольный участок размера
m×
n разбит на квадраты 1×1. Каждый квадрат является отдельным участком, соединенным калитками с соседними участками. При каких размерах участка можно обойти все квадратные участки, побывав в каждом по одному разу, и вернуться в первоначальный?
Решение
Раскрасим квадраты в шахматном порядке. При каждом переходе меняется цвет клетки, поэтому, если такой маршрут возможен, то только при четном числе клеток (возвращаемся в ту же клетку), т.е. или
m или
n четные числа. Осталось проверить, что при любых размерах обход возможен из любой клетки.
Источники и прецеденты использования
