2016 AMC 10B Problem 22

P21-25~6 minPrint

Games & Processes Basic Counting Map the objects to something easier to count Count the complement and subtract from the total

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 without answering

Key insight

There are 21 teams. A trio is not a cycle exactly when one team beat both others; each team does that in 45 trios, so 1330 - 945 = 385.

Solution

Step 1: how many teams? Each team played $10 + 10 = 20$ games, one against every other team. So there are $20$ other teams, $21$ teams in all.

Step 2: count all groups of three.
$\binom{21}{3} = \frac{21 \cdot 20 \cdot 19}{6} = 1330.$

Step 3: what can happen inside a group of three? Three games are played inside the group. Either

the results go around in a circle ( $A$ beats $B$ , $B$ beats $C$ , $C$ beats $A$ ), which is what we want, or
they do not, and then some team won both of its games inside the group. Only one team can do that, because two teams cannot both beat each other.

Counting circles directly is hard, so count the other kind and subtract.

Step 4: count groups where one team beat both others. Such a group is fixed by choosing the "boss" team and then two of the teams it beat.

Each of the $21$ teams beat $10$ teams, and it can choose two of them in $\binom{10}{2} = 45$ ways.
Each such group has exactly one boss, so no group is counted twice. That gives $21 \cdot 45 = 945$ groups.

Step 5: subtract.
$1330 - 945 = 385.$

The answer is $\boxed{\textbf{(A)}\ 385}$ .

Why this works

Circles are hard to count directly, but every group of three that is not a circle has exactly one team that beat the other two. Picking that team and two of its wins counts those groups with no repeats. When the thing you want is awkward to count, count everything else and subtract.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Each team played $10 + 10 = 20$ games, one against every other team, so there are $21$ teams and $\binom{21}{3} = 1330$ sets of three teams.

Look at the three games inside any set of three teams. Either the results form a cycle ( $A$ beats $B$ , $B$ beats $C$ , $C$ beats $A$ ), or they do not; and if they do not, then some team won both of its games in the set. Exactly one team can do so (two teams cannot both beat each other), so each non-cyclic triple is identified by its dominant team together with two of that team's victims.

Count non-cyclic triples by dominant team: each of the $21$ teams beat $10$ others, giving $\binom{10}{2} = 45$ pairs of victims, for
$21 \cdot 45 = 945$
non-cyclic triples in total.

The cyclic triples are what remain:
$1330 - 945 = 385.$

The answer is $\boxed{\textbf{(A)}\ 385}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
Intermediate Counting & Probability, Chapter 4: Constructive Counting and 1-1 Correspondences (§4.4, §4.5, §4.6)