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