Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Canadian MO Problems/Problem 4"
 
(3 intermediate revisions by one other user not shown)
Line 6: Line 6:
 
(b) Find the maximum number of cycle triplets possible.
 
(b) Find the maximum number of cycle triplets possible.
 
==Solution==
 
==Solution==
−
{{solution}}
 
−
(a) The answer is 0 cycle triplets. There is no possible value less than it, and it can be achieved if team <math>T_i</math> beats team <math>T_j</math> for all <math>i>j</math>.
 
−
(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 <math>\dbinom{2n+1}{3}</math> triplets, so we count the minimum number of "dominant" triplets.
 
  
−
Note that a "dominant" triplet is uniquely determined by the dominant team. Let team <math>T_i</math> have <math>a_i</math> wins in the tournament. Then choosing any pair of those teams that <math>T_i</math> beat and joining them with <math>T_i</math> gives exactly one "dominant" triplet. Thus, the number of dominant triplets is <math>\sum_{i=1}^{n} \dbinom{a_i}{2}</math>.
 
−
But since exactly <math>\dbinom{2n+1}{2}</math> games were played, <math>\sum_{i=1}^{n} a_i = \dbinom{2n+1}{2}</math>.
 
  
−
<math>\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}</math>.
+
[[Image:CMO2006Question4.jpg |700px]]
 +
 
  
 
==See also==
 
==See also==
Line 19: Line 15:
  
 
{{CanadaMO box|year=2006|num-b=3|num-a=5}}
 
{{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>.
 

Latest revision as of 17:20, 28 November 2023

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

CMO2006Question4.jpg


See also

2006 Canadian MO (Problems)
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 Followed by
Problem 5
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Canadian_MO_Problems/Problem_4&oldid=206229"