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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.