Задача
COM-B2-M04-P019 Король турнира
Докажите, что в любом турнире найдётся вершина \(v\), из которой до любой другой вершины можно добраться по направленному пути длины не более \(2\).
Выберите вершину с максимальным числом исходящих дуг.
Выберем вершину \(v\) с максимальной исходящей степенью. Пусть \(u\) — вершина, в которую нет дуги из \(v\). Тогда в турнире обязательно \(u\to v\).
Предположим, что ни один исходящий сосед \(w\) вершины \(v\) не имеет дуги \(w\to u\). Тогда для каждого такого \(w\) дуга направлена \(u\to w\). Кроме того, \(u\to v\). Значит, \(u\) побеждает всех, кого побеждает \(v\), и ещё саму вершину \(v\). У \(u\) исходящих дуг больше, чем у \(v\), противоречие.
Следовательно, найдётся исходящий сосед \(w\) вершины \(v\), для которого \(w\to u\). Тогда \(v\to w\to u\). Для вершин, которые \(v\) побеждает напрямую, путь имеет длину \(1\). Поэтому \(v\) достигает всех вершин за не более чем \(2\) шага.
Задача сильная, потому что экстремальный выбор не является самым длинным путём; нужно выбрать максимум исходящей степени.