В стране 1000 городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.

а1- авиакомпания 1

а2-авиакомпания 2

Пусть из некоторого города A нельзя попасть в некоторый город B по а1. Рассмотрим множество M всех городов, в которые можно попасть из города A по а1. Множество городов, не входящих в M, обозначим N. Множество N непусто, поскольку в нём содержится город B. Ясно, что из городов множества M нельзя попасть в города множества N по а1.

 Докажем, что из каждого города в любой другой можно попасть по а2.

 Если один из городов принадлежит M, а другой – множеству N, то между ними есть прямая авиалиния а2.

 Пусть два города принадлежат M. Тогда из первого города можно попасть по а2 в некоторый город множества N, а оттуда (также по а2) – во второй город.

 Аналогично рассматривается случай, когда оба города принадлежат N.