|
|
 |
Условие
На соревнованиях по фигурному велосипедированию было 100 судей. Каждый судья упорядочил всех участников (от лучшего по его мнению – к худшему). Оказалось, что ни для каких трёх участников A, B, C не нашлось трёх судей, один из которых считает, что A – лучший из трёх, а B – худший, другой – что B лучший, а C худший, а третий – что C лучший, а A худший. Докажите, что можно составить общий рейтинг участников так, чтобы для каждых двух участников A и B тот, кто выше в рейтинге, был бы лучше другого по мнению хотя бы половины судей.
Решение
Построим граф, вершинами которого будут участники, и от A будет идти ориентированное ребро к B, если A лучше B по мнению хотя бы 51 судьи (в этом случае мы будем писать A → B). Таким образом, A и B не будут соединены ребром ровно тогда, когда каждый лучше другого по мнению ровно 50 судей.
Заметим, что если A → B и B → C, то A → C. Действительно, предположим противное: C лучше A по мнению хотя бы 50 судей. Мы знаем, что B лучше A по мнению не более 49 судей; значит, найдётся судья, который считает, что C лучше A, а A лучше B. Аналогично, найдётся судья, считающий, что B лучше C, а C лучше A, а также судья, считающий, что A лучше B, а B лучше C. Но это противоречит условию. Докажем индукцией по n, что в ориентированном графе на n вершинах, для которого выполнено доказанное утверждение, можно пронумеровать вершины так, чтобы каждая стрелка шла от меньшего числа к большему. Для n = 100 это эквивалентно утверждению задачи.База (n = 2) очевидна.
Шаг индукции. Достаточно доказать, что найдётся вершина A, из которой не выходит ни одной стрелки. Тогда можно этой вершине присвоить номер n, выбросить её и перенумеровать остальные вершины по предположению индукции.
Предположим, что такой вершины нет. Тогда из каждой вершины выходит стрелка. Выйдем из любой вершины и будем двигаться по направлению стрелок. Рано или поздно мы попадём в вершину, в которой уже были; таким образом, в графе найдётся ориентированный цикл:
A1 → A2 → ... → Ak → A1. Но тогда, как доказано выше, A1 → A2 → A1. Противоречие.
Замечания
Можно облегчить решение, применив следующий трюк. Введём 101-го судью, мнение которого будет совпадать с мнением 100-го. Достаточно доказать, что в новой ситуации можно составить общий рейтинг так, чтобы любые два участника были упорядочены так, как считает большинство судей (тогда в исходной ситуации так будет считать не менее половины). Дальнейшее решение несколько облегчается, поскольку в этом случае каждые вершины соответствующего графа будут соединены ребром.
