Difference between revisions of "2006 Canadian MO Problems/Problem 4"

Revision as of 00:59, 28 October 2022

Problem

Consider a round robin tournament with $2n+1$ teams, where two teams play exactly one match and there are no ties. We say that the teams $X$ , $Y$ , and $Z$ form a cycle triplet if $X$ beats $Y$ , $Y$ beats $Z$ , and $Z$ beats $X$ .

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

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

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it. (a) The answer is 0 cycle triplets. There is no possible value less than it, and it can be achieved if team $T_i$ beats team $T_j$ for all $i>j$ . (b) Every triplet of teams is either a cycle triplet or a "dominant" triplet(One team defeats the two others). There are a total of $\dbinom{2n+1}{3}$ triplets, so we count the minimum number of "dominant" triplets.

Note that a "dominant" triplet is uniquely determined by the dominant team. Let team $T_i$ have $a_i$ wins in the tournament. Then choosing any pair of those teams that $T_i$ beat and joining them with $T_i$ gives exactly one "dominant" triplet. Thus, the number of dominant triplets is $\sum_{i=1}^{n} \dbinom{a_i}{2}$ . But since exactly $\dbinom{2n+1}{2}$ games were played, $\sum_{i=1}^{n} a_i = \dbinom{2n+1}{2}$ .

$\sum_{i=1}^{n} \dbinom{a_i}{2}=\frac{\sum_{i=1}^{n} {a_{i}^{2}} - \sum_{i=1}^{n} a_i}{2}=\frac{\sum_{i=1}^{n} {a_{i}^{2}} - \dbinom{2n+1}{2}}{2}$ .

@@ Line 19: / Line 19: @@
 {{CanadaMO box|year=2006|num-b=3|num-a=5}}
-(a) Clearly the answer is 0.
-(b) By using complementary counting, it is not hard to find that the answer is <math>\dfrac{n(n+1)(2n+1)}{6}</math>.

2006 Canadian MO (Problems)
Preceded by Problem 3	1 • 2 • 3 • 4 • 5	Followed by Problem 5

Page

Toolbox

Search

Difference between revisions of "2006 Canadian MO Problems/Problem 4"

Revision as of 00:59, 28 October 2022

Problem

Solution

See also