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

Пронумеруем олигархов и их города числами от до соответственно.

Пример.

Пусть дорога между городами и принадлежит олигарху под номером тогда и только тогда, когда Тогда количество дорог равно

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

Оценка 1.

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

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

Предположим, что это не так. Выбраниая тройка олигархов может быть сопоставлена всего трем дорогам (если таковые имеются): дороге принадлежащей олигарху дороге принадлежащей и дороге принадлежащей Легко видеть, что каким бы двум из этих дорог ни была сопоставлена тройка эта тройка олигархов сможет образовать корпорацию. Следовательно, каждая тройка олигархов сопоставлена не более одной дороге, т. е. дорог не более

Заметим, что в нашем примере любая тройка олигархов сопоставлена дороге принадлежащей олигарху т. е. всего дорог, что дает комбинаторный способ подсчета количества дорог в примере.

Оценка 2.

Рассмотрим граф, в котором вершиины — это города, а ребра цвета — дороги, принадлежащие олигарху номер Заметим, что если из графа, удовлетворяющего условию задачи, удалить часть вершин, выходящие из них ребра и все ребра, принадлежащие олигархам-владельцам удаляемых вершин, то для оставшегося графа условие задачи о невозможности построить корпорацию продолжит выполняться.

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

База очевидна.

Переход. Пусть мы хотим удалить олигарха номер . Так как все олигархов не могут образовать корпорацию, граф на. ребрах всех цветов несвязен. Обозначим через компоненту связности, содержащую город олигарха номер , через — объединение всех остальных компонент связности, а через и — количество вершин в и соответственно. Тогда подграф содержит не более ребер -го цвета. Далее, из вершины выходит не более ребер с цветами, соответствующими вершинам из Наконец, применяя к графу индукционное предположение, получаем, что в графе имеется не более ребер, имеющих цвет или выходящих из вершины Следовательно, при удалешии вершины исчезнет не более

ребер.

Для доказательства оценки будем по одной удалять вершины, подсчитывая, сколько ребер при этом пропадает. Получается, что мы удалили не более ребер. Заметим, что если в нашем примере удалять олигархов в порядке убывания номеров, то при удалении олигарха номер будет пропадать в точности ребер. Следовательно, в любом графе ребер не больше, чем в построенном нами примере.