Olympiad Maths Prep

Track / Stage 7 / 150 of 300 #1550 of 2000

Problem 1550

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.3 Prove it

n4n \geq 4 players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players badbad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let wiw_i and lil_i be respectively the number of wins and losses of the ii-th player. Prove that i=1n(wili)30.\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.

[i]Proposed by Sung Yun Kim, South Korea[/i]

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Define Variables and Initial Conditions:
Let n4 n \geq 4 be the number of players in the tournament. Each player i i has wi w_i wins and li l_i losses. Since every player plays exactly one game with every other player, we have:
wi+li=n1for all i. w_i + l_i = n - 1 \quad \text{for all } i.

2. Sum of Wins and Losses:
Since each game results in one win and one loss, the total number of wins is equal to the total number of losses:
i=1nwi=i=1nli=S1. \sum_{i=1}^n w_i = \sum_{i=1}^n l_i = S_1.

3. Sum of Squares of Wins and Losses:
The number of configurations where a player A A beats players B B and C C is given by:
i=1n(wi2)=i=1n(li2). \sum_{i=1}^n \binom{w_i}{2} = \sum_{i=1}^n \binom{l_i}{2}.
This implies:
i=1nwi2=i=1nli2=S2. \sum_{i=1}^n w_i^2 = \sum_{i=1}^n l_i^2 = S_2.

4. Sum of Cubes of Wins and Losses:
The number of configurations where a player A A beats players B B , C C , and D D is given by:
i=1n(wi3)=i=1n(li3). \sum_{i=1}^n \binom{w_i}{3} = \sum_{i=1}^n \binom{l_i}{3}.
This implies:
i=1nwi3i=1nli3=S3. \sum_{i=1}^n w_i^3 \geq \sum_{i=1}^n l_i^3 = S_3.

5. **Expression for (wili)3\sum (w_i - l_i)^3:**
Using the identity wi+li=n1=m w_i + l_i = n - 1 = m , we can express wili w_i - l_i as:
wili=m2li. w_i - l_i = m - 2l_i.
Therefore:
i=1n(wili)3=i=1n(m2li)3. \sum_{i=1}^n (w_i - l_i)^3 = \sum_{i=1}^n (m - 2l_i)^3.

6. Expand and Simplify the Cubic Expression:
Expanding (m2li)3 (m - 2l_i)^3 :
(m2li)3=m36m2li+12mli28li3. (m - 2l_i)^3 = m^3 - 6m^2 l_i + 12m l_i^2 - 8l_i^3.
Summing over all players:
i=1n(m2li)3=i=1n(m36m2li+12mli28li3). \sum_{i=1}^n (m - 2l_i)^3 = \sum_{i=1}^n (m^3 - 6m^2 l_i + 12m l_i^2 - 8l_i^3).
This simplifies to:
i=1n(m36m2li+12mli28li3)=nm36m2S1+12mS28S3. \sum_{i=1}^n (m^3 - 6m^2 l_i + 12m l_i^2 - 8l_i^3) = nm^3 - 6m^2 S_1 + 12m S_2 - 8 S_3.

7. **Relate to (liwi)3\sum (l_i - w_i)^3:**
Similarly, we have:
i=1n(liwi)3=i=1n((wili))3=i=1n(wili)3. \sum_{i=1}^n (l_i - w_i)^3 = \sum_{i=1}^n (- (w_i - l_i))^3 = -\sum_{i=1}^n (w_i - l_i)^3.
Therefore:
Θ=i=1n(wili)3=Θ. \Theta = \sum_{i=1}^n (w_i - l_i)^3 = -\Theta.

8. Conclusion:
Since Θ=Θ\Theta = -\Theta, it follows that:
ΘΘ    Θ0. \Theta \geq -\Theta \implies \Theta \geq 0.

The final answer is i=1n(wili)30 \boxed{ \sum_{i=1}^n (w_i - l_i)^3 \geq 0 } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.