Задача
COM-B2-M04-P013 Путь в турнире
В турнире между любыми двумя вершинами проведена ровно одна направленная дуга. Докажите, что все вершины турнира можно расположить в порядке \(v_1,v_2,\ldots,v_n\) так, что для каждого \(i\) дуга направлена из \(v_i\) в \(v_{i+1}\).
Возьмите самый длинный направленный путь и попробуйте вставить вершину, которая в него не вошла.
Выберем направленный путь максимальной длины \(v_1\to v_2\to\cdots\to v_k\). Предположим, что есть вершина \(u\), не лежащая на пути.
Если \(u\to v_1\), то можно поставить \(u\) перед \(v_1\), получив более длинный путь. Поэтому \(v_1\to u\). Если \(v_k\to u\), то можно поставить \(u\) после \(v_k\), значит, \(u\to v_k\).
Идя слева направо, найдём первый индекс \(j\), для которого \(u\to v_j\). Тогда \(j>1\), а по минимальности \(j\) имеем \(v_{j-1}\to u\). Следовательно, можно вставить \(u\) между \(v_{j-1}\) и \(v_j\): \(v_1\to\cdots\to v_{j-1}\to u\to v_j\to\cdots\to v_k\). Это более длинный путь, противоречие.
Значит, внешней вершины нет, и путь содержит все вершины.
Стандартная олимпиадная техника: максимальный путь плюс вставка внешней вершины.