2
$\begingroup$

$n\geq 5$ people of different ages play badminton. Each player plays four times, each time against a different player. Prove that there exists a player who beats two people older than her, or who beats two people younger than her.

Since each player plays four times, the average number of wins is two. So there exists a player winning at least two games. But how can we include the age condition?

$\endgroup$

2 Answers 2

2
$\begingroup$

Suppose there is not.

  • Then nobody can win more than two games.
  • So everybody wins exactly two games.
  • So the youngest player wins two games.
  • Contradiction.

So there is at least one example.

$\endgroup$
1
$\begingroup$

If some person $p$ beats $n\ge3$ people, then this is trivial, as there must be two people out of the $n$ people younger or older than $p,$ at the same time (pigeonhole principle).
If everyone beats exactly $2$ people, then consider the youngest person $p_0:$ this person beats two people, and these two people are older than $p_0$ by assumption, so this player $p_0$ is as required.
And we generalise this problem to the following

Proposition
Assume given $n\gt2$ points $p_1,\cdots,p_n,$ and, for each pair $(p_i,p_j),$ an integer $n(i,j)\in\{0,1\}$ such that $n(i,j)+n(j,i)=1, \forall i\not=j$ and $n(i,i)=0, \forall i.$ Then $\exists i=1,\cdots,n$ such that either the set $\{j\gt i\mid n(i,j)=1\}$ or the set $\{j\lt i\mid n(i,j)=1\}$ is of cardinality $\gt\frac{n-1}{4}.$
Proof.
Define $W_i=|\{j\not=i\mid n(i,j)=1\}|, W^+_i=|\{j\gt i\mid n(i,j)=1\}|,$ and $W_i^-=\{j\lt i\mid n(i,j)=1\},$ so $W_i=W^+_i+W^-_i.$
It is evident that $\sum_iW_i/n=(n-1)/2.$ And we consider two cases:
I. If there is $i_0$ such that $W_{i_0}\gt(n-1)/2,$ then one of $W_{i_0}^+$ and $W_{i_0}^-$ must be $\gt(n-1)/4$ II. If $W_{i}=(n-1)/2, \forall i,$ then $W_1=W^+_1\gt(n-1)/4.$
$\square$

Hope this helps.

$\endgroup$

You must log in to answer this question.

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