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