In a round-robin tournament, each team plays every other team exactly once. Show that if no games end in ties, then no matter what the outcomes of the games, there will be some way to number the teams so that team 1 beat team 2, and team 2 beat team 3, and team 3 beat team 4,
and so on.
I have the base case of two teams, call them Team A and Team B. Whichever team wins, will be renamed Team 1 and whichever team loses will be renamed Team 2 so that Team 1 beats Team 2. I know that I need to make an inductive hypothesis about having $n$ teams, so that I can prove it for $n+1$ teams, but I have no idea how to go about it.
Best Answer
Consider a round-robin tournament with $n + 1$ teams. Arbitrarily pick a particular team, say team $x$. Then by the definition of a round-robin tournament with no ties, observe that we can partition the remaining $n$ teams into two sets $W$ and $L$ of size $a$ and $b$ respectively, where $W$ is the set of all winners who beat team $x$ and $L$ is the set of all losers that team $x$ managed to beat (so that $a + b = n$). Then since $a,b \leq n$, it follows by the inductive hypothesis that we can relabel the teams so that $W = \{w_1, w_2, \ldots, w_a\}$ and $L = \{\ell_1, \ell_2, \ldots, \ell_b\}$, where: $$ w_1 \xrightarrow{\text{beats}} w_2 \xrightarrow{\text{beats}} \cdots \xrightarrow{\text{beats}} w_a $$ $$ \ell_1 \xrightarrow{\text{beats}} \ell_2 \xrightarrow{\text{beats}} \cdots \xrightarrow{\text{beats}} \ell_b $$ But then we can order all $n+1$ teams as follows: $$ w_1 \xrightarrow{\text{beats}} w_2 \xrightarrow{\text{beats}} \cdots \xrightarrow{\text{beats}} w_a \xrightarrow{\text{beats}} x \xrightarrow{\text{beats}} \ell_1 \xrightarrow{\text{beats}} \ell_2 \xrightarrow{\text{beats}} \cdots \xrightarrow{\text{beats}} \ell_b $$