Задача 111897

Темы:    [ Обход графов ] [ Шахматная раскраска ] [ Четность и нечетность ] [ Целочисленные решетки (прочее) ]

Сложность: 4 Классы: 6,7,8,9

Условие

Автор: Ященко И.В.

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.

Решение

  Пример. Один из возможных маршрутов туриста изображён на рисунке слева. Двигаясь по этому пути, турист пройдёт 34 улицы (улицей мы называем отрезок между двумя соседними перекрёстками).

  Оценка. Всего в Старом городе 36 перекрёстков. Всякий раз, когда турист проходит очередную улицу, он попадает на новый перекрёсток. Таким образом, больше 35 улиц турист пройти не сможет (начальный перекрёсток A не считается). Покажем, что посетить 35 перекрёстков (и, следовательно, пройти 35 улиц) турист тоже не сможет. Для этого раскрасим перекрёстки в чёрный и белый цвета в шахматном порядке (рис. справа). Всякий раз, проходя улицу, турист попадает на перекрёсток другого цвета. И отель, и вокзал расположены на белых перекрёстках. Поэтому любой маршрут содержит чётное число улиц, а число 35 нечётно.

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

олимпиада
Название	Математический праздник
год
Год	2009
Класс
Класс	6
задача
Номер	5