0

how can i prove this

Let n > 1 be an integer. Suppose there are n teams in a football league and every two teams have played against each other exactly once with no ties. Prove that it is possible to number the teams 1 to n such that at the end of the season team i beats team i + 1 for i = 1,...,n − 1.

I proved this by for example giving n 3 or 4, but what exactly this question want ?

funky-nd
  • 111
  • Can you show what you did for $n=3$? What is it that is unclear to you? – MarkG Feb 28 '15 at 12:19
  • the first team beats second and third, the second team beats third, so first team 2win 0lose second team 1win 1lose third team 0win 2lose – funky-nd Feb 28 '15 at 12:20
  • If $T_1$ beat $T_2$ who beat $T_3$ who beat $T_1$, there is no first team, but you can still number them so $T_i$ beat $T_{i+1}$. – Empy2 Feb 28 '15 at 15:15
  • the Q needs explaining, @Michael proves all three W1L1. If i=4 and n=10, the teams to consider are 5,6,...,12,13? You could wrap, but your statement appears to be false. – JMP Mar 18 '15 at 07:13

2 Answers2

1

Suppose the first $n-1$ have been arranged as asked. Try to show that it is possible either
1) to slot the nth team between two teams, or
2) that the nth team beat the first of the $n-1$, or
3) that the nth team lost to the last of the $n-1$.

Empy2
  • 50,853
-1

Define the $n$ teams as $T_i, 1\le i\le n$, and the win/lose relation as $\gt$ where $T_i$ beats $T_j$ iff $i\lt j$, so for example $T_2$ beats $T_3$. This means $T_1$ wins $n-1$ games, $T_2$ wins $n-2$ games and so on, with $T_n$ winning zero games. As each team has won a different number of games, your question has been answered.

JMP
  • 21,771