B6 Турниры и линейные порядки

Метод состоит в том, что задачу о результатах соревнований (турниров), рейтингах или частичных порядках сводят к анализу ориентированного графа, где вершины — участники, а дуги — результаты игр.

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

Аналогия из жизни: школьный чемпионат по шахматам, где каждый сыграл с каждым. По итоговым очкам можно восстановить много информации о структуре турнира, даже не зная результатов отдельных партий.

Ключевое свойство, которое делает этот метод мощным: в любом турнире существует гамильтонов путь — линейная расстановка всех участников, где каждый победил следующего. Это означает, что любой турнир имеет «линеаризацию», и мы всегда можем расположить участников в цепочку побед.

• Теорема о гамильтоновом пути: В любом турнире (полном ориентированном графе) существует гамильтонов путь. Условие: каждая пара вершин соединена ровно одной дугой. Когда использовать: нужно доказать, что участников можно линейно упорядочить по «кто кого побил».

• Формула суммы очков: Если в турнире $n$ участников, сыграно $\binom{n}{2}$ игр, то суммарное число очков всех участников равно $\binom{n}{2}$ (при системе 1 за победу, 0 за поражение$). *$Условие: ничьих нет. Когда использовать:* для оценок — если у кого-то очков слишком много/мало, получаем противоречие.

• Теорема о «короле»: Участник с наибольшим числом побед является «королём»: он победил каждого, кого не победил напрямую, через одного посредника. Условие: у «короля» строго максимальное число побед (или среди тех, кто набрал максимум$). *$Когда использовать:* задачи про «лучшего участника» с транзитивностью.

• Подсчёт через полустепени: $\sum_{v} d^+(v) = \binom{n}{2}$, где $d^+(v)$ — число побед участника $v$. Отсюда средний результат равен $\frac{n-1}{2}$. Когда использовать: оценки числа «сильных» участников (набравших больше среднего).

• Индукция по числу участников. Для доказательства гамильтонова пути: предположи, что путь есть для $n-1$ участников, и вставь $n$-го в нужное место цепочки.
• Суммирование очков для получения противоречия. Если условие требует невозможного количества побед — посчитай суммарно и покажи противоречие с $\binom{n}{2}$.
• Разбивка на «сильных» и «слабых» участников. Тех, кто набрал больше/меньше $\frac{n-1}{2}$, рассматривать отдельно.
• Ориентированный граф и его свойства. Нарисовать граф для малых $n$ (4–5 участников) и найти паттерн.
• Метод крайнего элемента. Взять участника с максимальным числом побед и анализировать его отношения с остальными — часто именно он является «королём».
• Перебор турнирных таблиц для малых $n$ чтобы найти пример или контрпример.

Поверхностные признаки (что буквально написано):
- В условии слова «турнир», «каждый сыграл с каждым», «круговая система».
- Участники набирают очки: «за победу — 1 очко, за поражение — 0».
- Есть вопросы о рейтинге, линейном порядке, «лучшем участнике».

Структурные признаки (форма выражения, объекты):
- Отношение «$A$ лучше $B$» задано для каждой пары, но оно нетранзитивно (возможны циклы $A > B > C > A$).
- Нужно построить линейную расстановку или доказать её существование.
- Задача про сумму показателей всех участников.

Цель задачи (что от тебя хотят):
- Доказать, что существует участник, победивший всех (или через одного посредника).
- Найти или доказать существование линейного порядка по результатам.
- Показать, что при данных условиях на очки такая турнирная таблица возможна/невозможна.

Задача 1. Существование «транзитивной цепочки» в турнире

Условие: В турнире участвовали $n$ команд, каждые две сыграли между собой ровно один матч, ничьих не было. Докажите, что команды можно пронумеровать $1, 2, \ldots, n$ так, что команда $i$ победила команду $i+1$ для всех $i = 1, \ldots, n-1$.

Источник: классическая олимпиадная задача (тренировочная)

Как думать (рассуждение ученика):
1. Вижу: «каждые две сыграли», «нет ничьих» — это в точности определение турнирного графа. Триггер: «пронумеровать так, что $i$ победила $i+1$» — это гамильтонов путь.
2. Метод: теорема о гамильтоновом пути в турнире. Доказываю индукцией.
3. Первый ход: база — $n=2$: один победил другого, нумеруем. Предположим верно для $n-1$.
4. Ключевая идея: есть цепочка $v_1, v_2, \ldots, v_{n-1}$ (по индукции). Нужно вставить $v_n$. Три случая: $v_n$ проиграл $v_1$ — ставим $v_n$ первым; $v_n$ победил $v_{n-1}$ — ставим последним; иначе найдём $i$: $v_n$ победил $v_i$, но проиграл $v_{i-1}$ — вставляем между ними.

Решение:
Индукция по $n$. База: $n=2$ — очевидно.

Предположим, что для $n-1$ участников цепочка $v_1 \to v_2 \to \cdots \to v_{n-1}$ построена. Добавляем $n$-го участника $u$.

• Если $u$ проиграл $v_1$: ставим $u$ на первое место: $u \to v_1 \to v_2 \to \cdots \to v_{n-1}$.
• Если $u$ победил $v_{n-1}$: ставим $u$ последним: $v_1 \to \cdots \to v_{n-1} \to u$.
• Иначе: пусть $u$ победил $v_j$ для каких-то $j$, но проиграл $v_1$. Возьмём наименьшее $i$ такое, что $u$ победил $v_i$. Тогда $u$ проиграл $v_{i-1}$ (по выбору минимального $i$). Вставляем: $v_1 \to \cdots \to v_{i-1} \to u \to v_i \to \cdots \to v_{n-1}$.

Во всех случаях гамильтонов путь для $n$ участников построен.

Ответ: Доказано по индукции.

Что в этой задаче было главным для понимания метода: индуктивное «вклинивание» нового элемента в уже готовую цепочку — это стандартный приём для турниров, который нужно знать наизусть.

Задача 2. Турнир с условием на очки

Условие: В турнире из 7 команд (круговая система, победа — 1 очко, поражение — 0) оказалось, что все команды набрали разное число очков. Докажите, что команда, занявшая 3-е место, победила команды, занявшие 4-е, 5-е, 6-е и 7-е места.

Источник: олимпиадная задача (тренировочная)

Как думать (рассуждение ученика):
1. $n=7$, все очки различны. Всего очков: $\binom{7}{2} = 21$. Все различны — значит очки: $0, 1, 2, 3, 4, 5, 6$ (единственный вариант с суммой 21).
2. Команда 3-го места набрала 4 очка. Она победила 4 команды и проиграла 2.
3. Команды с 4-го по 7-е набрали $3, 2, 1, 0$ очков. Нужно доказать, что все они проиграли команде с 4 очками.
4. Предположим противное: команда с $k < 4$ очками победила третью (4 очка). Тогда у третьей только 3 победы + проигрыш этой команде. Но команды 1-го и 2-го места набрали 6 и 5 очков — они тоже победили третью? Сосчитаем:
Третья проиграла командам 1-й и 2-й (6 и 5 очков) — это 2 поражения. Значит, она победила все оставшиеся 4 команды (4–7 места).

Решение:
Распределение очков: $6, 5, 4, 3, 2, 1, 0$. Команда с 4 очками — 3-е место. Она проиграла двум командам (кому именно — следует из распределения). Команды с 5 и 6 очками — 1-е и 2-е места. Команда 3-го места не могла проиграть никому из нижней четвёрки, иначе имела бы $\leq 3$ побед, то есть $\leq 3$ очков — противоречие. Значит, она победила всех с местами 4–7.

Ответ: Доказано.

Что в этой задаче было главным: использование единственности распределения очков ($0, 1, \ldots, 6$) при условии «все различны» — это автоматическое следствие формулы суммы очков.

• Ошибка: предполагать, что «лучший» победил всех. В турнире циклы возможны ($A > B > C > A$). → Не путай «набрал больше всего очков» с «победил всех»; используй теорему о «короле».
• Ошибка: забыть, что гамильтонов путь не единственен. Думать, что найденная расстановка — единственная. → В задаче на доказательство существования этого достаточно, но задачи на единственность требуют отдельного анализа.
• Ошибка: неверно применить формулу суммы очков при наличии ничьих. Если в условии ничьи возможны, формула $\binom{n}{2}$ для суммы не работает. → Проверяй условие задачи на наличие ничьих.
• Ошибка: перепутать «победил $k$ команд» и «набрал $k$ очков». При стандартной системе это одно и то же, но если за ничью дают пол-очка — нет. → Уточняй систему начисления очков.
• Ошибка: в индуктивном шаге не проверить случай «крайнего вставления». При вставке нового элемента не рассмотреть случаи «ставим первым» или «ставим последним». → Явно разбирай все три случая.