Maths Olympiad Prep

Library / /94 of 94

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

In a chess tournament there are nn players (where n>1n > 1 is odd), and every two players play against each other exactly once. It is known that exactly nn games end in a tie. For any set SS of players including AA and BB, we say that AA admires BB in SS if
(a) AA does not beat BB; or
(b) there exists a sequence of other distinct players C1,C2,,CkC_1, C_2, \dots, C_k in SS such that AA does not beat C1C_1; CkC_k does not beat BB; and CiC_i does not beat Ci+1C_{i+1} for 1ik11 \le i \le k-1.
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 nn) the greatest possible number of harmonic sets.

Solution

The answer is n(n3)(n2+6n31)48\frac{n(n-3)(n^2+6n-31)}{48}.

For each kk, let dkd_k be the number of games that player kk wins. Note that
S:=d1+d2++dn=(n2)n=n(n3)2. S := d_1 + d_2 + \dots + d_n = \binom{n}{2} - n = \frac{n(n-3)}{2}.
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 NN of harmonic sets is at most
(n4)k=1n(dk3). \binom{n}{4} - \sum_{k=1}^{n} \binom{d_k}{3}.
Note that the binomial function (x3)\binom{x}{3} is convex. So we can use the majorization inequality to get
N(n4)n(n323)=n(n3)(n2+6n31)48. N \le \binom{n}{4} - n \binom{\frac{n-3}{2}}{3} = \frac{n(n-3)(n^2+6n-31)}{48}.
It remains to show that this bound is attainable.

Suppose the game between player kk and player k+1k+1 ends in a tie for all kk, where player n+1n+1 means player 1. For any other game between player ii and player jj where 1i<jn1 \le i < j \le n, player jj beats player ii if and only if ij(mod2)i \equiv j \pmod 2.
For even kk, player kk beats players 2,4,,k22, 4, \dots, k-2 and k+3,k+5,,nk+3, k+5, \dots, n. So player kk has won n32\frac{n-3}{2} games. For odd k<nk < n, player kk beats players 1,3,,k21, 3, \dots, k-2 and k+3,k+5,,n1k+3, k+5, \dots, n-1. So player kk has won n32\frac{n-3}{2} games. Also, player nn beats players 3,5,,n23, 5, \dots, n-2. So player nn has won n32\frac{n-3}{2} 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 SS of four players a,b,c,da, b, c, d such that none of them beats everyone else in this set.

* If there is no tie among the games played between a,b,c,da, b, c, d, then WLOG we may assume player aa beats players bb and cc. By the assumption, player dd must beat player aa. Since player dd does not beat everyone else, WLOG assume player bb beats player dd. If player cc beats player bb, then we have the cycle acbdaa \to c \to b \to d \to a, and so the set is harmonic. If player cc beats player dd, WLOG assume player bb beats player cc. Then we have the cycle abcdaa \to b \to c \to d \to a, and so the set is harmonic.

The only case left is that both players bb and dd beat player cc, which means player cc is beaten by everyone else. This holds when each of a,b,da, b, d is less than and has different parity as cc, or is greater than and has the same parity as cc. WLOG assume a<b<da < b < d.
- If a<b<d<ca < b < d < c, then player dd beats everyone else, contradiction.
- If a<b<c<da < b < c < d, then player bb beats everyone else, contradiction.
- If a<c<b<da < c < b < d, then player aa beats everyone else, contradiction.
- If c<a<b<dc < a < b < d, then player dd beats everyone else, contradiction.

* If there is a tie in the game played between cc and dd, then cc and dd are consecutive integers, or are 11 and nn. By the construction, it is impossible that both cc and dd beat the same player, or are beaten by the same player. (This is the place where we have used nn is odd, since otherwise 11 and nn are beaten by some players in the same construction of the even case.)

WLOG assume player aa does not beat player cc, and player dd does not beat player aa. If the same holds when aa is replaced by bb, then we have a cycle cadcbdcc \to a \to d \to c \to b \to d \to c, 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 bb does not beat player dd, and player cc does not beat player bb, then we also have a cycle cadbcc \to a \to d \to b \to c, and so the set is harmonic.

This shows the construction works. So the proof is complete.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.