Problem
COM-B2-M04-P013 A Path in a Tournament
In a tournament, between any two vertices exactly one directed edge is drawn. Prove that all vertices can be ordered as \(v_1,v_2,\ldots,v_n\) so that for every \(i\), the edge is directed from \(v_i\) to \(v_{i+1}\).
Take a longest directed path and try to insert a vertex not on it.
Choose a directed path of maximum length \(v_1\to v_2\to\cdots\to v_k\). Suppose there is a vertex \(u\) outside the path.
If \(u\to v_1\), then \(u\) can be placed before \(v_1\), giving a longer path. Hence \(v_1\to u\). If \(v_k\to u\), then \(u\) can be placed after \(v_k\), so \(u\to v_k\).
Moving from left to right, let \(j\) be the first index such that \(u\to v_j\). Then \(j>1\), and by the minimality of \(j\) we have \(v_{j-1}\to u\). Thus \(u\) can be inserted between \(v_{j-1}\) and \(v_j\): \(v_1\to\cdots\to v_{j-1}\to u\to v_j\to\cdots\to v_k\). This is a longer path, a contradiction.
Therefore no outside vertex exists, and the path contains all vertices.
A standard olympiad technique: a longest path plus insertion of an outside vertex.