Olympiad Maths Prep

Library / /8 of 13

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

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 iith player. Prove that
i=1n(wii)30 \sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3} \geq 0

Solutions — 2

Solution 1

For any tournament TT satisfying the problem condition, denote by S(T)S(T) 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_{ij}=1 if the iith player wins against the jjth one, and εij=1\varepsilon_{ij}=-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_{ij}\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\{j_{1}, j_{2}, j_{3}\}} \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_{|\{i, j_{1}, j_{2}, j_{3}\}|=4} \varepsilon_{i j_{1}} \varepsilon_{i j_{2}} \varepsilon_{i j_{3}}+P(T) \sum_{i \neq j} \varepsilon_{ij}=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_{ij}=-\varepsilon_{ji}, 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 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}\{i, j_{1}, j_{2}, j_{3}\} 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 this equality exactly once, as well as in the left-hand part. Clearly, there are no other terms in both parts, so the equality is established.

Solution 2

Similarly to the first solution, we call the subsets of players as companies, and the kk-element subsets will be called as kk-companies.

In any company of the players, call a player the local champion of the company if he defeated all other members of the company. Similarly, if a player lost all his games against the others in the company then call him the local loser of the company. Obviously every company has at most one local champion and at most one local loser. By the condition of the problem, whenever a 4-company has a local loser, then this company has a local champion as well.

Suppose that kk is some positive integer, and let us count all cases when a player is the local champion of some kk-company. The iith player won against wiw_{i} other player. To be the local champion of a kk-company, he must be a member of the company, and the other k1k-1 members must be chosen from those whom he defeated. Therefore, the iith player is the local champion of (wik1)\binom{w_{i}}{k-1} kk-companies. Hence, the total number of local champions of all kk-companies is i=1n(wik1)\sum_{i=1}^{n}\binom{w_{i}}{k-1}.

Similarly, the total number of local losers of the kk-companies is i=1n(ik1)\sum_{i=1}^{n}\binom{\ell_{i}}{k-1}.

Now apply this for k=2,3k=2,3 and 4.

Since every game has a winner and a loser, we have i=1nwi=i=1ni=(n2)\sum_{i=1}^{n} w_{i}=\sum_{i=1}^{n} \ell_{i}=\binom{n}{2}, and hence
i=1n(wii)=0 \sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)=0
In every 3-company, either the players defeated one another in a cycle or the company has both a local champion and a local loser. Therefore, the total number of local champions and local losers in the 3-companies is the same, i=1n(wi2)=i=1n(i2)\sum_{i=1}^{n}\binom{w_{i}}{2}=\sum_{i=1}^{n}\binom{\ell_{i}}{2}. So we have
i=1n((wi2)(i2))=0 \sum_{i=1}^{n}\left(\binom{w_{i}}{2}-\binom{\ell_{i}}{2}\right)=0
In every 4-company, by the problem's condition, the number of local losers is less than or equal to the number of local champions. Then the same holds for the total numbers of local champions and local losers in all 4-companies, so i=1n(wi3)i=1n(i3)\sum_{i=1}^{n}\binom{w_{i}}{3} \geq \sum_{i=1}^{n}\binom{\ell_{i}}{3}. Hence,
i=1n((wi3)(i3))0 \sum_{i=1}^{n}\left(\binom{w_{i}}{3}-\binom{\ell_{i}}{3}\right) \geq 0
Now we establish the problem statement as a linear combination of the above. It is easy check that
(xy)3=24((x3)(y3))+24((x2)(y2))(3(x+y)24)(xy) (x-y)^{3}=24\left(\binom{x}{3}-\binom{y}{3}\right)+24\left(\binom{x}{2}-\binom{y}{2}\right)-\left(3(x+y)^{2}-4\right)(x-y)
Apply this identity to x=wix=w_{i} and y=iy=\ell_{i}. Since every player played n1n-1 games, we have wi+i=n1w_{i}+\ell_{i}=n-1, and thus
(wii)3=24((wi3)(i3))+24((wi2)(i2))(3(n1)24)(wii). \left(w_{i}-\ell_{i}\right)^{3}=24\left(\binom{w_{i}}{3}-\binom{\ell_{i}}{3}\right)+24\left(\binom{w_{i}}{2}-\binom{\ell_{i}}{2}\right)-\left(3(n-1)^{2}-4\right)\left(w_{i}-\ell_{i}\right) .
Then

\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)^{3}=24 \underbrace{\sum_{i=1}^{n}\left(\binom{w_{i}}{3}-\binom{\ell_{i}}{3}\right)}_{\geq 0}+24 \underbrace{\sum_{i=1}^{n}\left(\binom{w_{i}}{2}-\binom{\ell_{i}}{2}\right)}_{0}-\left(3(n-1)^{2}-4\right) \underbrace{\sum_{i=1}^{n}\left(w_{i}-\ell_{i}\right)}_{0} \geq 0 .

Looking for a route rather than 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.