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.
P.S: Added another approach which didn't lead to answer.
Thanks and sorry for my English.
Best Answer
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$