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

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$

Tags:

Combinatorics

Discrete Mathematics

Induction

Related

When does the game end? How to prove closure property for $x\cdot y = \frac{x + y}{1 + \frac{xy}{c^2}}$? Is there a group $G$ and subgroup $H$, such that there exists $g\in G$ with $gHg^{-1} \subset H$ and $|H:gHg^{-1}|$ is infinite? Compute fundamental group _visually_ by the polygonal representation of the space Almost normal subgroups: Is there any notion which is weaker than normal subgroup? Corollary of the Malgrange Preparation Theorem Integral check. Is partial fractions the only way? Show that $\forall x>0,\;\frac{1}{x}+x\geq 2$ Uniqueness of pair $\left(a,b\right)$ in writing positive integer $V$ as $V=a^2+ab+b^2$ with $a, b \in \mathbb{N}$ Proving the identity $\tan x+2\tan2x+4\tan4x+8\cot8x=\cot x$ by considering a more general form Why do we divide Permutations to get to Combinations? Smallest $1\ 000$ digit number $x$ , such that $x$ , $x+2$ and $x+6$ are all prime?

Recent Posts