2016 AMC 10B Problem 22

Problem 22 of 25HarderCombinatorics

A set of teams held a round-robin tournament in which every team played every other team exactly once. Every team won

10

games and lost

10

games; there were no ties. How many sets of three teams

\{A, B, C\}

were there in which

A

beat

B,

B

beat

C,

and

C

beat

A?

Show solution

Solution

The total number of teams is

10+10+1=21.

The total number of sets is therefore

\binom{21}{3} = 1330.

Now, we must subtract the total number of sets such that there is no cycle. This only happens if one team beats the other two teams. There are

21

choices for the team that beat the other two and

\binom{10}{2} = 45

ways to choose the teams they beat. Thus, the total of non-cycles is

21\cdot 45=945.

This means the total number of cycles is

1330-945=385.

Thus, the correct answer is A .

Tagged: graph theory · complementary counting · combinations