Задание №177239: Турнир городов

1. В первый день 2n школьников играли в пинг-понг «навылет»: сначала сыграли двое,
затем победитель сыграл с третьим, победитель этой пары — с четвёртым и т.д., по-
ка не сыграл последний школьник (ничьих в пинг-понге не бывает). Во второй день те же
школьники разыграли кубок: сначала произвольно разбились на пары и сыграли в парах, про-
игравшие выбыли, а победители снова произвольно разбились на пары и сыграли в парах, и

т.д. Оказалось, что наборы игравших пар в первый и во второй день были одни и те же
(возможно, победители были другие). Найдите наибольшее возможное значение n.
Б. Френкин
Ответ. 3.
Решение. Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Со-

гласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир
и выберем те партии, победители которых до этого не выигрывали (например, такова пер-
вая партия). Тогда соответствующие рёбра образуют путь, а остальные рёбра одним концом
примыкают к этому пути. В частности, если выбросить все висячие вершины, то останется
только наш путь без крайних вершин.
Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить
висячие вершины, останется граф турнира на 2n−1 победителях первого этапа. Он, очевидно,
является путём лишь при n ≤ 3, в противном случае победитель турнира будет иметь степень
не меньше 3. Значит, n ≤ 3.

Осталось привести пример при n = 3. Пусть участники пронумерованы от 1 до 8 и пары в
кубке таковы (первым указан проигравший, вторым победитель): 1–2, 3–4, 5–6, 7–8, 2–4, 6–8,
4–8. тогда при игре навылет пары могли быть такими (победитель снова указан вторым): 1–2,
2–4, 3–4, 4–8, 7–8, 8–6, 6–5.