6
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ 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$ $\endgroup$
    – amir na
    Feb 21, 2019 at 18:31
  • $\begingroup$ @amirna I think I have untangled it now $\endgroup$
    – Henry
    Feb 21, 2019 at 18:52
1
$\begingroup$

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

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .