Соответствия, сравнения, количества

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

Для организации авиасообщения силами компаний присоединим к Дезориентации ещё города: теперь городов стало Докажем индукцией по что требуемому условию для городов можно удовлетворить с помощью авиакомпаний. База очевидна. Если утверждение доказано для сначала обслужим одними и теми же компаниями две страны из городов (по отдельности), а затем объединим эти страны и все рейсы между половинами поручим выполнять -й авиакомпании, причём летать она будет только из первой страны во вторую.

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