Consider a round-robin tournament with $2 n+1$ teams, where each team plays each other team exactly once. We say that three teams $X, Y$ and $Z$, form a cycle triplet if $X$ beats $Y, Y$ beats $Z$, and $Z$ beats $X$. There are no ties.

(a) Determine the minimum number of cycle triplets possible.

(b) Determine the maximum number of cycle triplets possible.
(a) The minimum is 0, which is achieved by a tournament in which team \( T_i \) beats \( T_j \) if and only if \( i > j \).

(b) Any set of three teams constitutes either a cycle triplet or a "dominated triplet" in which one team beats the other two; let there be \( c \) of the former and \( d \) of the latter. Then \( c + d = \binom{2n+1}{3} \). Suppose that team \( T_i \) beats \( x_i \) other teams; then it is the winning team in exactly \( \binom{x_i}{2} \) dominated triples. Observe that \( \sum_{i=1}^{2n+1} x_i = \binom{2n+1}{2} \), the total number of games. Hence

\[
d = \sum_{i=1}^{2n+1} \binom{x_i}{2} = \frac{1}{2} \sum_{i=1}^{2n+1} x_i^2 - \frac{1}{2} \binom{2n+1}{2}
\]

By the Cauchy-Schwarz Inequality, \( (2n+1) \sum_{i=1}^{2n+1} x_i^2 \geq \left( \sum_{i=1}^{2n+1} x_i \right)^2 = n^2 (2n+1)^2 \), whence

\[
c = \binom{2n+1}{3} - \sum_{i=1}^{2n+1} \binom{x_i}{2} \leq \binom{2n+1}{3} - \frac{n^2 (2n+1)}{2} + \frac{1}{2} \binom{2n+1}{2} = \frac{n(n+1)(2n+1)}{6}.
\]

To realize the upper bound, let the teams be \( T_1 = T_{2n+2}, T_2 = T_{2n+3}, \cdots, T_i = T_{2n+1+i}, \cdots, T_{2n+1} = T_{4n+2} \). For each \( i \), let team \( T_i \) beat \( T_{i+1}, T_{i+2}, \cdots, T_{i+n} \) and lose to \( T_{i+n+1}, \cdots, T_{i+2n} \). We need to check that this is a consistent assignment of wins and losses, since the result for each pair of teams is defined twice. This can be seen by noting that \( (2n+1+i) - (i+j) = 2n+1-j \geq n+1 \) for \( 1 \leq j \leq n \). The cycle triplets are \( (T_i, T_{i+j}, T_{i+j+k}) \) where \( 1 \leq j \leq n \) and \( (2n+1+i) - (i+j+k) \leq n \), i.e., when \( 1 \leq j \leq n \) and \( n+1-j \leq k \leq n \). For each \( i \), this counts \( 1 + 2 + \cdots + n = \frac{1}{2} n(n+1) \) cycle triplets. When we range over all \( i \), each cycle triplet gets counted three times, so the number of cycle triplets is

\[
\frac{2n+1}{3} \left( \frac{n(n+1)}{2} \right) = \frac{n(n+1)(2n+1)}{6}.
\]