LV OM - III - Task 3

In a certain tournament, $ n $ players participated $ (n \geq 3) $. Each played against each other exactly once, and there were no draws. A three-element set of players is called a draw triplet if the players can be numbered in such a way that the first won against the second, the second against the third, and the third against the first. Determine the maximum number of draw triplets that could have appeared in the tournament.
Instead of determining the maximum number of draw triples, we will determine the minimum number of non-draw triples.
Let's number the players from 1 to $ n $ and assume that player number $ i $ won $ x_i $ times. Then the total number of matches is






Each non-draw triple is uniquely determined by the player who won against the other two players in that triple. Therefore, player number $ i $ determines $ x_i \choose 2 $ non-draw triples, and the total number of non-draw triples in the tournament is






In the further part of the solution, we will consider two cases:


The number $ n $ is odd, i.e., $ n = 2k + 1 $. Then, by the inequality between the quadratic mean and the arithmetic mean, we obtain






Thus, the number of draw triples does not exceed






The above number of draw triples will occur only when each player wins exactly $ k $ times (equality holds in inequality (1) at that time). Such a result of the matches can be achieved in the following way. We seat the players around a round table and assume that each of them won only against the players sitting to their right at a distance of no more than $ k $ places. In such a setup of matches, each player won exactly $ k $ times.

The number $ n $ is even, i.e., $ n = 2k $. Then $ (x_i - k)(x_i - k + 1) \geq 0 $ for $ i = 1,2,\ldots,n $, from which we obtain $ x_i^2 \geq (2k - 1)x_i - k(k - 1) $. Therefore,






From this, it follows that the number of draw triples does not exceed






The above number of draw triples will occur only when each player wins $ k $ or $ k-1 $ times (equality holds in inequality (2) at that time). Such a result of the matches can be achieved in the following way. As above, we seat the players around a round table and assume that each of them won against the players sitting to their right at a distance of no more than $ k-1 $ places. The result of the match between players sitting opposite each other is determined arbitrarily. In this way, each player won $ k $ or $ k-1 $ times.


Summarizing: the maximum number of draw triples that can appear in the tournament is $ \frac{1}{24}n(n^2 - 1) $ if $ n $ is an odd number, and $ \frac{1}{24}n(n^2 - 4) $ if $ n $ is an even number.