In a chess tournament there are players (where is odd), and every two players play against each other exactly once. It is known that exactly games end in a tie. For any set of players including and , we say that admires in if
(a) does not beat ; or
(b) there exists a sequence of other distinct players in such that does not beat ; does not beat ; and does not beat for .
A set of four players is said to be harmonic if each of the four players admires everyone else in the set. Find (in terms of ) the greatest possible number of harmonic sets.
Solution
The answer is .
For each , let be the number of games that player wins. Note that
Observe that for a set of four players, if one of them beats everybody else, then the set is not harmonic. Also, there cannot be two players beating everybody else in the set simultaneously. Therefore, the number of harmonic sets is at most
Note that the binomial function is convex. So we can use the majorization inequality to get
It remains to show that this bound is attainable.
Suppose the game between player and player ends in a tie for all , where player means player 1. For any other game between player and player where , player beats player if and only if .
For even , player beats players and . So player has won games. For odd , player beats players and . So player has won games. Also, player beats players . So player has won games. This shows all players have won the same number of games. Therefore, the equality of the majorization inequality holds.
We now show that for any set of four players in which nobody beats everyone else, it is harmonic. Once this is shown, all equalities in the above deduction hold, which means the bound is attained. Suppose on the contrary that there exists a non-harmonic set of four players such that none of them beats everyone else in this set.
* If there is no tie among the games played between , then WLOG we may assume player beats players and . By the assumption, player must beat player . Since player does not beat everyone else, WLOG assume player beats player . If player beats player , then we have the cycle , and so the set is harmonic. If player beats player , WLOG assume player beats player . Then we have the cycle , and so the set is harmonic.
The only case left is that both players and beat player , which means player is beaten by everyone else. This holds when each of is less than and has different parity as , or is greater than and has the same parity as . WLOG assume .
- If , then player beats everyone else, contradiction.
- If , then player beats everyone else, contradiction.
- If , then player beats everyone else, contradiction.
- If , then player beats everyone else, contradiction.
* If there is a tie in the game played between and , then and are consecutive integers, or are and . By the construction, it is impossible that both and beat the same player, or are beaten by the same player. (This is the place where we have used is odd, since otherwise and are beaten by some players in the same construction of the even case.)
WLOG assume player does not beat player , and player does not beat player . If the same holds when is replaced by , then we have a cycle , and so the set is harmonic. (Although the cycle does not consist of distinct players, we can easily shorten the sequence so that it only consists of distinct players.) If player does not beat player , and player does not beat player , then we also have a cycle , and so the set is harmonic.
This shows the construction works. So the proof is complete.