Задача 60632

Темы:    [ Четность и нечетность ] [ Обход графов ] [ Степень вершины ]

Сложность: 3+ Классы: 8,9,10

Условие

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

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

Решение

  Оценка. Аналогично решению задачи 97840 доказываем, что длина маршрута не меньше  60 + 16 : 2 = 68.
  Доказательство возможности обхода. "Раздвоим" 8 улиц (см. рисунок). Теперь в графе 68 рёбер, и все его вершины чётны. Согласно решению задачи 30806 в нём есть эйлеров цикл.

Ответ

68.

Замечания

Нетрудно построить и конкретный пример обхода по аналогии с рисунком в решении задачи 97840.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	1
Название	Четность
Тема	Четность и нечетность
задача
Номер	04.006