Обход дачного посёлка
*
Опубликовано:
28.06.2011
Категория:
Сложность:
Участок прямоугольной формы разбит на квадраты, образующие n рядов по m квадратов в каждом ряду. Каждый квадрат является отдельным участком, соединённым калитками со всеми соседними участками. При каких n и m можно обойти все квадратные участки, побывав в каждом по одному разу, и вернуться в первоначальный?
Подсказка
Нужно мысленно раскрасить участки в шахматном порядке.
Решение
Раскрасим квадраты в шахматном порядке. При каждом переходе меняется цвет квадрата. Поэтому, если такой маршрут возможен, то число шагов должно быть чётным, то есть n или m чётно. Осталось проверить, что в этом случае искомый маршрут возможен:
(Случай чётного n аналогичен с точностью до поворота изображения на 90°)
Добавить комментарий