Difference between revisions of "2006 Canadian MO Problems/Problem 4"
| Line 7: | Line 7: | ||
==Solution== | ==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>. | ||
==See also== | ==See also== | ||
Revision as of 16:21, 23 May 2020
Problem
Consider a round robin tournament with 
teams, where two teams play exactly one match and there are no ties. We say that the teams 
, 
, and 
form a cycle triplet if beats , beats , and beats .
(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 
beats team 
for all 
.
(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 
triplets, so we count the minimum number of "dominant" triplets.
Note that a "dominant" triplet is uniquely determined by the dominant team. Let team have 
wins in the tournament. Then choosing any pair of those teams that beat and joining them with gives exactly one "dominant" triplet. Thus, the number of dominant triplets is 
.
But since exactly 
games were played, 
.
.
See also
| 2006 Canadian MO (Problems) | ||
| Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 | Followed by Problem 5 |
(a) Clearly the answer is 0.
(b) By using complementary counting, it is not hard to find that the answer is 
.
