1
$\begingroup$

Problem: Eight players entered a round-robin tennis tournament. At the end of the tournament, a player who wins $N$ sets will take home $N^2$ dollars. The entry fee is $17.50 per player. Why is this enough to pay for the prizes?

Intuitive solution: Trying to maximize the total prize, we see that the eight players can take home as much as $7^2 + \ldots + 1^2+0^2=\$140$ dollars. So $\$140\div8 \text{ players}=\$17.50$ as entry fee for each player is enough.

What is a rigorous proof for this problem?

$\endgroup$
3
$\begingroup$

Denote by $x_k$ the number of victories for player $P_k$, and assume $x_1\leq x_2\leq\ldots\leq x_8$. If $x_8<7$ then $P_8$ has lost at least one game against a player $P_k$ with $k<8$. Since $$(x_8+1)^2+(x_k-1)^2=x_8^2+x_k^2+2(x_8-x_k)+2\geq x_8^2+x_k^2+2\ ,$$ the total payout would have been greater when $P_8$ would have won this game as well. It follows that in the case of maximal payout player $P_8$ wins all his games. Therefore we may assume this from now on and start arguing about player $P_7$. If $x_7<6$, then $P_7$ has lost at least one game against a player $P_k$ with $k<7$, and so on.

(Of course this could and should be converted to a full-fledged induction proof.)

It follows that the total payout $W$ is maximal if $x_k=k-1$ $\>(1\leq k\leq 8)$, so that $$W_\max=\sum_{j=1}^7 j^2={7\cdot 8\cdot 15\over 6}=140\ ,$$ which leads to an entrance fee of ${140\over8}=17.50$ dollars.

| cite | improve this answer | |
$\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.