Обход дачного посёлка

*

Сложность: 

Участок прямоугольной формы разбит на квадраты, образующие n рядов по m квадратов в каждом ряду. Каждый квадрат является отдельным участком, соединённым калитками со всеми соседними участками. При каких n и m можно обойти все квадратные участки, побывав в каждом по одному разу, и вернуться в первоначальный?

Подсказка

Нужно мысленно раскрасить участки в шахматном порядке.

Решение

Раскрасим квадраты в шахматном порядке. При каждом переходе меняется цвет квадрата. Поэтому, если такой маршрут возможен, то число шагов должно быть чётным, то есть n или m чётно. Осталось проверить, что в этом случае искомый маршрут возможен:

(Случай чётного n аналогичен с точностью до поворота изображения на 90°)




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.