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

Проект МЦНМО
при участии
школы 57
Задача 65077
Темы:    [ Теория алгоритмов (прочее) ]
[ Теория графов (прочее) ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

В Швамбрании некоторые города связаны двусторонними беспосадочными авиарейсами. Рейсы разделены между тремя авиакомпаниями, причём если какая-то авиакомпания обслуживает линию между городами А и Б, то самолёты других компаний между этими городами не летают. Известно, что из каждого города летают самолёты всех трёх компаний. Докажите, что можно, вылетев из некоторого города, вернуться в него, воспользовавшись по пути рейсами всех трёх компаний и не побывав ни в одном из промежуточных городов дважды.


Решение

Вылетим из любого города А первой компанией, попадем в город Б, из него вылетим второй компанией, далее третьей, затем снова первой, второй, третьей и т.д. Рассмотрим самый первый момент, когда на этом пути встретился город В, где мы уже были. Тогда кусок нашего пути от первого посещения города В до второго и будет искомым. В самом деле, если мы в первый раз вылетели из города В в город Г, то из Г сразу вернуться в В мы не могли. Поэтому между двумя посещениями города В мы совершили хотя бы три перелёта и, значит, воспользовались по пути рейсами всех трёх компаний.

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

олимпиада
Название Олимпиада имени Леонарда Эйлера (для 8 классов)
год/номер
Номер 2 (2010)
тур
задача
Номер 2

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

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