ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60632
Темы:    [ Четность и нечетность ]
[ Обход графов ]
[ Степень вершины ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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

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


Решение

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


Ответ

68.

Замечания

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

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

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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .