Назад

Задание олимпиады: маршрут по квадратному городу 5×5

Задача 160632 • Сложность: 2 • 8-10 класс
Задача

Город имеет форму квадрата 5×5:

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

  Оценка. Аналогично решению задачи 197840 доказываем, что длина маршрута не меньше  60 + 16 : 2 = 68.

  Доказательство возможности обхода. "Раздвоим" 8 улиц (см. рисунок). Теперь в графе 68 рёбер, и все его вершины чётны. Согласно решению задачи 130806 в нём есть эйлеров цикл.

Ответ

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Войти Зарегистрироваться
Комментариев нет