Олимпиада имени Леонарда Эйлера2009-2010 учебный год, I тур заключительного этапа

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

Комментарий/решение

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