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 (South Korea)
Solution
For any tournament satisfying the problem condition, denote by the 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 (2) 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 (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.