Maths Olympiad Prep

Library / /16 of 20

Combinatorics Difficulty 6.6 National olympiad Prove it Greece

Twelve friends play a tennis tournament, where each player plays exactly one game with each of the eleven other players. The winner wins one point and the loser gets zero points, while there is no tie. If the number of points of the players are B1,B2,...,B12B_1, B_2, ..., B_{12}, find the maximum value of Σ3=B13+B23++B123\Sigma_3 = B_1^3 + B_2^3 + \dots + B_{12}^3.

Solution

The 12 friends will play (122)=12112=66\binom{12}{2} = \frac{12 \cdot 11}{2} = 66 games, so the total number of points from all games is 6666. One possible outcome of the tournament is to put all players in an order and each of them to win all players that are after of him in the order. Then the first one has 1111 points, the second one 1010 points and so on. Then the last one has 00 points, and all the players have a different number of points from 00 to 1111. Then:
Σ3=03+13++113=(11122)2=662 \Sigma_3 = 0^3 + 1^3 + \dots + 11^3 = \left(\frac{11 \cdot 12}{2}\right)^2 = 66^2
We will prove that this is the maximum value for Σ3\Sigma_3.
Indeed, suppose that there is another outcome of the tournament which gives maximum Σ3\Sigma_3 and in that tournament the players AA and BB have the same number of points, let it be κ\kappa, where AA won BB. We observe that κ0\kappa \neq 0 since AA won against BB. A new outcome will be produced if we suppose that BB won against AA, so AA would have κ1\kappa - 1 points and BB will have κ+1\kappa + 1 points. If all the other games had the same outcome, then the difference between the new Σ3\Sigma_3 and the old one will be
(κ+1)3+(κ1)32κ3=6κ>0, (\kappa + 1)^3 + (\kappa - 1)^3 - 2\kappa^3 = 6\kappa > 0,
so the new Σ3\Sigma_3 is greater than the old one which we supposed that has the maximum Σ3\Sigma_3, a contradiction.
It follows that the maximum Σ3\Sigma_3 equals to 66266^2 and is reached with the above example.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.