Задача
На соревнованиях по фигурному велосипедированию было 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. Противоречие.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь