Problem 1416

Solution:

Take the natural graph theoretic interpretation, where an edge points towards the loser of each pair, and call such a line an alternating path. Consider the longest alternating path, and suppose it doesn't contain everyone. We will show we can make the path longer, which would be a contradiction.

First, assume the path has an odd number of vertices, labeled $v_{1}, \ldots, v_{n}$. WLOG $v_{1}$ points towards $v_{2}$, $v_{3}$ points towards $v_{2}$, all the way up to $v_{n}$ which points towards $v_{n-1}$ (otherwise, reverse all the edges). Also WLOG $v_{1}$ points towards $v_{n}$ (if not, label the vertices backwards). Let $w$ be a vertex not in the path. Note that if $v_{n}$ points towards $w$, we can make the path longer by adding $w$ to the end. Thus, $w$ must point towards $v_{n}$. But now we can take the path $w, v_{n}, v_{1}, \ldots, v_{n-1}$, which is longer than before, and so a contradiction.

Now assume the path has an even number of vertices, labeled $v_{1}, \ldots, v_{n}$, and WLOG $v_{1}$ points towards $v_{2}$ again. Then $v_{n-1}$ will point towards $v_{n}$. Since 1000 is even, there are at least 2 vertices not in the path, say $w_{1}$ and $w_{2}$. If either one points towards $v_{n}$, we can add it to the end of the path, so $v_{n}$ must point towards both. Similarly, they must both point towards $v_{1}$. But now note that if $v_{n-1}$ points to either, we can make the path $v_{1}, \ldots, v_{n-1}, w_{i}, v_{n}$, which is longer. Thus, $w_{1}, w_{2}$ must both point towards $v_{n-1}$. Now restrict our attention to $v_{1}, \ldots, v_{n-1}$. Note that $w_{1}, w_{2}$ both point towards both ends, so we can WLOG assume $v_{1}$ points towards $v_{n-1}$. Also WLOG $w_{1}$ points towards $w_{2}$. Then we can form the path $w_{2}, w_{1}, v_{n-1}, v_{1}, \ldots, v_{n-2}$, which has $n+1$ vertices. Thus, if the longest alternating path does not contain every vertex, we can make it longer, which is a contradiction, so there must exist an alternating path with all 1000 vertices.