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