# Prove that the maximum score difference between two consecutive teams in a tournament with $n$ teams is $n$

There are $$n$$ teams in a tournament. Every two teams play with each other once (so there is $$n(n-1)/2$$ games at all). The scores are: Win: 2, Draw: 1, Lose: 0. At the last ranking table, team in the $$i$$-th place has $$S_i$$ points. ( $$S_1 \geq S_2 \geq S_3 \geq ... \geq S_n$$) we want to prove that $$S_{i-1} - S_{i} \leq n ;~~~ 2\leq i\leq n$$.

For the proof, I wanted to use induction. If we think $$n-1$$ is satisfied, then if we add the $$n$$-th team, in the worst situation if it wins all the games and all the teams in previous games have $$n-2$$ points (all equal), then we get $$S_{new} - S_{first~Place~Before~Adding~New} = 2(n-1) - (n-2) = n$$. But the problem is I cannot prove that it is actually the worst situation. for example I cannot say if $$S_{i} - S_{i-1} = n-1$$ before adding the $$n$$-th team, what will happen if I add $$n$$-th team?

P.S: Another approach is proof by contradiction. Let $$S_i - S_{i-1} \geq n+1$$. Suppose this happens for the first and second place. first place has $$a$$ points and all others have at most $$a-n-1$$ then if we solve $$(n-1)(a-n-1) + a \geq n(n-1)/2 \times2$$ (Sum of the scores at the and is number of games *2). then we get $$a\geq 2n -1/n -1$$. It is completely impossible for all other teams to have more than $$2n-1/n-1 - n -1$$ points. The problem is that I supposed that the $$n+1$$ point difference occurs between first and second place. I cannot generalize this method to other situations.

So I think this question should have another proof without using induction. So I think I need new ideas to solve this. Maybe the problem is easier than this and I am thinking in a wrong way and I want to find a good approach to solve this problem.

Thanks and sorry for my English.

Hint:

A. Show $$S_{i} \ge n-i$$ or $$S_{i+1} \ge n-i-1$$ by considering the lowest possible score of the best of the worst $$n-i$$ teams:

The worst $$n-i$$ teams play $$\frac{(n-i)(n-i-1)}{2}$$ matches between them and so score at least a total of $$(n-i)(n-i-1)$$ points so the best of them scores at least $$n-i-1$$

B. Show $$S_{i-1} \le 2n-i$$ or $$S_{i} \le 2n-i-1$$ by considering the highest possible score of the worst of the best $$i$$ teams:

The best $$n-i$$ teams are involved in $$\frac{n(n-1)}{2}-\frac{(n-i)(n-i-1)}{2}$$ matches and so score no more than a total of $$n(n-1) - (n-i)(n-i-1) = i(2n-i -1)$$ points so the best of them scores at least $$2n-i -1$$

C. So $$S_{i-1}-S_{i} \le (2n-i)- (n-i) = n$$ and $$S_{i}-S_{i+1} \le (2n-i-1)- (n-i-1) = n$$

• I think my notation in the question is somehow ambiguous. Actually the $S_1$ has more score than $S_2$ because the first place has more score than second place. so actually the inequality becomes $S_{i-1} - S_{i} \leq n$. Can you edit your post so that it follow these scoring because I am not sure how did you numbered the scores. Actually $S_1 \geq S_2 \geq S_3 \geq ... \geq S_n$ – amir na Feb 21 at 18:31
• @amirna I think I have untangled it now – Henry Feb 21 at 18:52

As each game results in $$2$$ points being awarded, the sum of all scores at the end of the tournament will be $$n(n-1)$$.

Suppose one team wins all of their $$n-1$$ games for a maximum total score of $$S_1=2(n-1)$$. Then the remaining $$n-1$$ teams will have a total of $$(n-2)(n-1)$$ points. The lowest score that the second place team can have occurs when all of these team have the same score, and that score is $$S_2=n-2$$. This give us a maximum difference of: $$S_1-S_2=2(n-1)-(n-2)=2n-2-n+2=n$$ If no team wins all of their games, then $$S_1<2(n-1)$$ and $$S_2>n-2$$ with the difference $$S_1-S_2

Similarly, if one team loses all their games $$(S_n=0)$$, the other teams will have an average score of $$n$$, so at least one will have a score $$S_{n-1}\le n$$