Maths Olympiad Prep

Library / /510 of 520

Combinatorics Difficulty 7.7 National olympiad, round 2 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 bad 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 i\ell_{i} be respectively the number of wins and losses of the ii th player. Prove that i=1n(wii)30 \sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0 (South Korea)

Solution

For any tournament TT satisfying the problem condition, denote by S(T)S(T) the sum under consideration, namely
S(T)=i=1n(wii)3 S(T)=\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3}
First, we show that the statement holds if a tournament TT has only 4 players. Actually, let A=(a1,a2,a3,a4)A=\left(a_{1}, a_{2}, a_{3}, a_{4}\right) be the number of wins of the players; we may assume that a1a2a3a4a_{1} \geq a_{2} \geq a_{3} \geq a_{4}. We have a1+a2+a3+a4=(42)=6a_{1}+a_{2}+a_{3}+a_{4}=\binom{4}{2}=6, hence a41a_{4} \leq 1. If a4=0a_{4}=0, then we cannot have a1=a2=a3=2a_{1}=a_{2}=a_{3}=2, otherwise the company of all players is bad. Hence we should have A=(3,2,1,0)A=(3,2,1,0), and S(T)=33+13+(1)3+(3)3=0S(T)=3^{3}+1^{3}+(-1)^{3}+(-3)^{3}=0. On the other hand, if a4=1a_{4}=1, then only two possibilities, A=(3,1,1,1)A=(3,1,1,1) and A=(2,2,1,1)A=(2,2,1,1) can take place. In the former case we have S(T)=33+3(2)3>0S(T)=3^{3}+3 \cdot(-2)^{3}>0, while in the latter one S(T)=13+13+(1)3+(1)3=0S(T)=1^{3}+1^{3}+(-1)^{3}+(-1)^{3}=0, as desired.

Now we turn to the general problem. Consider a tournament TT with no bad companies and enumerate the players by the numbers from 1 to nn. For every 4 players i1,i2,i3,i4i_{1}, i_{2}, i_{3}, i_{4} consider a "sub-tournament" Ti1i2i3i4T_{i_{1} i_{2} i_{3} i_{4}} consisting of only these players and the games which they performed with each other. By the abovementioned, we have S(Ti1i2i3i4)0S\left(T_{i_{1} i_{2} i_{3} i_{4}}\right) \geq 0. Our aim is to prove that
S(T)=i1,i2,i3,i4S(Ti1i2i3i4) S(T)=\sum_{i_{1}, i_{2}, i_{3}, i_{4}} S\left(T_{i_{1} i_{2} i_{3} i_{4}}\right)
where the sum is taken over all 4-tuples of distinct numbers from the set {1,,n}\{1, \ldots, n\}. This way the problem statement will be established.

We interpret the number (wii)3\left(w_{i}-\ell_{i}\right)^{3} as following. For iji \neq j, let εij=1\varepsilon_{i j}=1 if the ii-th player wins against the jj-th one, and εij=1\varepsilon_{i j}=-1 otherwise. Then
(wii)3=(jiεij)3=j1,j2,j3iεij1εij2εij3. \left(w_{i}-\ell_{i}\right)^{3}=\left(\sum_{j \neq i} \varepsilon_{i j}\right)^{3}=\sum_{j_{1}, j_{2}, j_{3} \neq i} \varepsilon_{i j_{1}} \varepsilon_{i j_{2}} \varepsilon_{i j_{3}}.
Hence,
S(T)=i{j1,j2,j3}εij1εij2εij3. S(T)=\sum_{i \notin\left\{j_{1}, j_{2}, j_{3}\right\}} \varepsilon_{i j_{1}} \varepsilon_{i j_{2}} \varepsilon_{i j_{3}}.
To simplify this expression, consider all the terms in this sum where two indices are equal. If, for instance, j1=j2j_{1}=j_{2}, then the term contains εij12=1\varepsilon_{i j_{1}}^{2}=1, so we can replace this term by εij3\varepsilon_{i j_{3}}. Make such replacements for each such term; obviously, after this change each term of the form εij3\varepsilon_{i j_{3}} will appear P(T)P(T) times, hence
S(T)={i,j1,j2,j3}=4εij1εij2εij3+P(T)ijεij=S1(T)+P(T)S2(T). S(T)=\sum_{\left|\left\{i, j_{1}, j_{2}, j_{3}\right\}\right|=4} \varepsilon_{i j_{1}} \varepsilon_{i j_{2}} \varepsilon_{i j_{3}}+P(T) \sum_{i \neq j} \varepsilon_{i j}=S_{1}(T)+P(T) S_{2}(T).
We show that S2(T)=0S_{2}(T)=0 and hence S(T)=S1(T)S(T)=S_{1}(T) for each tournament. Actually, note that εij=εji\varepsilon_{i j}=-\varepsilon_{j i}, and the whole sum can be split into such pairs. Since the sum in each pair is 0, so is S2(T)S_{2}(T).

Thus the desired equality (2) rewrites as
S1(T)=i1,i2,i3,i4S1(Ti1i2i3i4). S_{1}(T)=\sum_{i_{1}, i_{2}, i_{3}, i_{4}} S_{1}\left(T_{i_{1} i_{2} i_{3} i_{4}}\right).
Now, if all the numbers j1,j2,j3j_{1}, j_{2}, j_{3} are distinct, then the set {i,j1,j2,j3}\left\{i, j_{1}, j_{2}, j_{3}\right\} is contained in exactly one 4-tuple, hence the term εij1εij2εij3\varepsilon_{i j_{1}} \varepsilon_{i j_{2}} \varepsilon_{i j_{3}} appears in the right-hand part of (3) exactly once, as well as in the left-hand part. Clearly, there are no other terms in both parts, so the equality is established.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.