Назад
Задача

На соревнованиях по фигурному велосипедированию было 100 судей. Каждый судья упорядочил всех участников (от лучшего по его мнению – к худшему). Оказалось, что ни для каких трёх участников A, B, C не нашлось трёх судей, один из которых считает, что A – лучший из трёх, а B – худший, другой – что B лучший, а C худший, а третий – что C лучший, а A худший. Докажите, что можно составить общий рейтинг участников так, чтобы для каждых двух участников A и B тот, кто выше в рейтинге, был бы лучше другого по мнению хотя бы половины судей.

Решение

  Построим граф, вершинами которого будут участники, и от A будет идти ориентированное ребро к B, если A лучше B по мнению хотя бы 51 судьи (в этом случае мы будем писать  AB).  Таким образом, A и B не будут соединены ребром ровно тогда, когда каждый лучше другого по мнению ровно 50 судей.  Заметим, что если  AB  и  BC,  то  AC.  Действительно, предположим противное: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, выбросить её и перенумеровать остальные вершины по предположению индукции.   Предположим, что такой вершины нет. Тогда из каждой вершины выходит стрелка. Выйдем из любой вершины и будем двигаться по направлению стрелок. Рано или поздно мы попадём в вершину, в которой уже были; таким образом, в графе найдётся ориентированный цикл: A1A2→ ... →AkA1.  Но тогда, как доказано выше,  A1A2A1.  Противоречие.

Ответ

Ответ задачи отсутствует

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет