1

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.

UserX
  • 651
  • Start with 3 teams. Can you figure out why it is true then? Then 4 teams. Can you see a pattern? – almagest Sep 11 '14 at 21:33
  • @almagest I can see a pattern, but I have no idea how to translate that into something that makes sense when I write it down. – UserX Sep 11 '14 at 22:22

2 Answers2

5

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 $$

Adriano
  • 41,576
  • How do you justify that an arbitrary pick will yield a team that beats or is beaten by all other teams? – bob Sep 11 '14 at 21:40
  • @bob In a round-robin tournament, the arbitrary team $x$ must play all other $n$ teams, and there are no ties. – Adriano Sep 11 '14 at 21:41
  • Ahh, I misinterpreted the question as "beat = gained more points than overall" (introducing some arbitrary points system). +1 for not being silly. – bob Sep 11 '14 at 21:50
-1

A simple inductive proof. Easy for 2 teams. Assume you can do it for n team and consider n+1 team. Set aside Team "X". Arrange the n teams so that team k--> k+1. If X beats 1 then X --> 1 -->2...-->n. If not look for the first team j that X beats. Then: 1-->2-->...j-1 -->X -->j -->...n is your "inductive answer."

Moshe Rosenfeld
  • 1
  • 1
  • Your answer is hard to understand. After checking the already existing answer, I am wondering what additional content your answer provides that isn't already in the existing answers. –  Mar 03 '19 at 18:13