Комбинаторика на Питергоре

Покажем сначала, что всегда найдутся компаний, с помощью которых можно добраться от любой планеты до любой другой. Выберем произвольно компаний, назовем их стремительными, а остальные — надежными. Предположим, что посредством стремительных компаний нельзя добраться, скажем, с Венеры на Сатурн. Это значит, что Венеру и Сатурн соединяет рейс надежной компании, и любая другая планета соединена рейсом надежной компании либо с Венерой, либо с Сатурном. Отсюда следует, что с любой планеты до любой можно добраться рейсами надежных компаний (через Венеру и Сатурн). Добавляя к надежным компаниям любую стремительную, получаем требуемые компаний. Теперь приведем пример, показывающий, что компаний закрыть с выполнением требований удастся не всегда. Для каждого множества из 1008 авиакомпаний может найтись такая планета на которую летают только компании из Планет для выполнения такого требования нужно не более чем (общее число подмножеств множества компаний), а у нас их больше. При этом для любых двух планет их можно соединить рейсом компании из — это множество непусто. Как соединяются другие пары планет, неважно.Теперь при закрытии любого множества из компаний планета становится изолирована от остальной галактики.