Maths Olympiad Prep

Library / /187 of 520

Combinatorics Difficulty 6.2 National olympiad Find the answer

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

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

(b) Determine the maximum number of cycle triplets possible.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

(a) The minimum is 0, which is achieved by a tournament in which team Ti T_i beats Tj T_j if and only if i>j 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 c of the former and d d of the latter. Then c+d=(2n+13) c + d = \binom{2n+1}{3} . Suppose that team Ti T_i beats xi x_i other teams; then it is the winning team in exactly (xi2) \binom{x_i}{2} dominated triples. Observe that i=12n+1xi=(2n+12) \sum_{i=1}^{2n+1} x_i = \binom{2n+1}{2} , the total number of games. Hence

d=i=12n+1(xi2)=12i=12n+1xi212(2n+12) 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)i=12n+1xi2(i=12n+1xi)2=n2(2n+1)2 (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=(2n+13)i=12n+1(xi2)(2n+13)n2(2n+1)2+12(2n+12)=n(n+1)(2n+1)6. 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 T1=T2n+2,T2=T2n+3,,Ti=T2n+1+i,,T2n+1=T4n+2 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 i , let team Ti T_i beat Ti+1,Ti+2,,Ti+n T_{i+1}, T_{i+2}, \cdots, T_{i+n} and lose to Ti+n+1,,Ti+2n 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+1jn+1 (2n+1+i) - (i+j) = 2n+1-j \geq n+1 for 1jn 1 \leq j \leq n . The cycle triplets are (Ti,Ti+j,Ti+j+k) (T_i, T_{i+j}, T_{i+j+k}) where 1jn 1 \leq j \leq n and (2n+1+i)(i+j+k)n (2n+1+i) - (i+j+k) \leq n , i.e., when 1jn 1 \leq j \leq n and n+1jkn n+1-j \leq k \leq n . For each i i , this counts 1+2++n=12n(n+1) 1 + 2 + \cdots + n = \frac{1}{2} n(n+1) cycle triplets. When we range over all i i , each cycle triplet gets counted three times, so the number of cycle triplets is

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

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.