Browse · MathNet
Print51st IMO Shortlisted Problems
counting and probability
Problem
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 and be respectively the number of wins and losses of the th player. Prove that
Solution
For any tournament satisfying the problem condition, denote by sum under consideration, namely First, we show that the statement holds if a tournament has only 4 players. Actually, let be the number of wins of the players; we may assume that . We have , hence . If , then we cannot have , otherwise the company of all players is bad. Hence we should have , and . On the other hand, if , then only two possibilities, and can take place. In the former case we have , while in the latter one , as desired.
Now we turn to the general problem. Consider a tournament with no bad companies and enumerate the players by the numbers from 1 to . For every 4 players consider a "sub-tournament" consisting of only these players and the games which they performed with each other. By the abovementioned, we have . Our aim is to prove that where the sum is taken over all 4-tuples of distinct numbers from the set . This way the problem statement will be established.
We interpret the number as following. For , let if the th player wins against the th one, and otherwise. Then Hence, To simplify this expression, consider all the terms in this sum where two indices are equal. If, for instance, , then the term contains , so we can replace this term by . Make such replacements for each such term; obviously, after this change each term of the form will appear times, hence We show that and hence for each tournament. Actually, note that , and the whole sum can be split into such pairs. Since the sum in each pair is 0, so is .
Thus the desired equality rewrites as Now, if all the numbers are distinct, then the set is contained in exactly one 4-tuple, hence the term 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.
---
Alternative solution.
Similarly to the first solution, we call the subsets of players as companies, and the -element subsets will be called as -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 is some positive integer, and let us count all cases when a player is the local champion of some -company. The th player won against other player. To be the local champion of a -company, he must be a member of the company, and the other members must be chosen from those whom he defeated. Therefore, the th player is the local champion of -companies. Hence, the total number of local champions of all -companies is .
Similarly, the total number of local losers of the -companies is .
Now apply this for and 4.
Since every game has a winner and a loser, we have , and hence 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, . So we have 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 . Hence, Now we establish the problem statement as a linear combination of the above. It is easy check that Apply this identity to and . Since every player played games, we have , and thus 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 .
Now we turn to the general problem. Consider a tournament with no bad companies and enumerate the players by the numbers from 1 to . For every 4 players consider a "sub-tournament" consisting of only these players and the games which they performed with each other. By the abovementioned, we have . Our aim is to prove that where the sum is taken over all 4-tuples of distinct numbers from the set . This way the problem statement will be established.
We interpret the number as following. For , let if the th player wins against the th one, and otherwise. Then Hence, To simplify this expression, consider all the terms in this sum where two indices are equal. If, for instance, , then the term contains , so we can replace this term by . Make such replacements for each such term; obviously, after this change each term of the form will appear times, hence We show that and hence for each tournament. Actually, note that , and the whole sum can be split into such pairs. Since the sum in each pair is 0, so is .
Thus the desired equality rewrites as Now, if all the numbers are distinct, then the set is contained in exactly one 4-tuple, hence the term 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.
---
Alternative solution.
Similarly to the first solution, we call the subsets of players as companies, and the -element subsets will be called as -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 is some positive integer, and let us count all cases when a player is the local champion of some -company. The th player won against other player. To be the local champion of a -company, he must be a member of the company, and the other members must be chosen from those whom he defeated. Therefore, the th player is the local champion of -companies. Hence, the total number of local champions of all -companies is .
Similarly, the total number of local losers of the -companies is .
Now apply this for and 4.
Since every game has a winner and a loser, we have , and hence 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, . So we have 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 . Hence, Now we establish the problem statement as a linear combination of the above. It is easy check that Apply this identity to and . Since every player played games, we have , and thus 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 .
Techniques
Counting two waysAlgebraic properties of binomial coefficients