2012 AMC 10B Problem 15

P11-15~4 minPrint

Games & Processes Basic Counting Bound the quantity above/below or estimate to pin it down Consider the largest/smallest element or boundary case

In a round-robin tournament with 6 teams, each team plays one game against each other team, and each game results in one team winning and one team losing. At the end of the tournament, the teams are ranked by the number of games won. What is the maximum number of teams that could be tied for the most wins at the end of the tournament?

Show solution without answering

Key insight

There are 15 games, so 15 wins in total. Six teams can't share 15 wins equally, but five teams can each win 3 if they all beat the sixth team.

Solution

This asks for a maximum, so there are two parts: show that $6$ tied teams is impossible, then show that $5$ tied teams can really happen.

Part 1: six teams cannot all tie.

Count the games. Each of the $6$ teams plays the other $5$ , which is $6 \times 5 = 30$ , but that counts every game twice (once for each team). So there are $15$ games.
Each game gives exactly one win, so the six teams have $15$ wins altogether.
If all six tied, each would have $15 \div 6 = 2.5$ wins. That is not a whole number, so it can't happen.

Part 2: five teams can tie.

4. Call the teams $A, B, C, D, E$ and $F$ . Let $F$ lose every game. That gives each of $A$ through $E$ one win.
5. Now the five teams $A$ to $E$ play $10$ games among themselves. We want each of them to win exactly $2$ of their $4$ games. Seat them in a circle $A, B, C, D, E$ and let each team beat the next two teams around the circle:
- $A$ beats $B$ and $C$ ;
- $B$ beats $C$ and $D$ ;
- $C$ beats $D$ and $E$ ;
- $D$ beats $E$ and $A$ ;
- $E$ beats $A$ and $B$ .
6. Check that every game is listed exactly once: this list has $10$ results, and each pair of teams appears once (for example $A$ vs $D$ appears only as " $D$ beats $A$ ").
7. So each of $A$ through $E$ has $1 + 2 = 3$ wins, and $F$ has $0$ . Five teams are tied for the most wins.

Six is impossible and five is possible, so the maximum is $5$ .

The answer is $\boxed{\textbf{(D)}\ 5}$ .

Why this works

For "most teams tied" questions, the total number of wins is fixed, and it has to divide evenly among the tied teams. That gives the upper limit. Then you need an actual schedule to prove the limit can be reached. The circle trick, where each team beats the next few teams around, is a standard way to give an odd number of teams equal records.

Concise solution

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

There are $\binom{6}{2} = 15$ games, and each produces exactly one win, so the six win totals add to $15$ .

Could all six teams tie? Then each would have $15/6$ wins, not an integer. So at most $5$ teams can share the top spot.

Five is achievable. Call the teams $T_1, \dots, T_5$ and $L$ . Let $L$ lose all five of its games, which gives each $T_i$ one win. The $T_i$ play $\binom52 = 10$ games among themselves; arrange them around a circle and let each team beat the next two teams clockwise and lose to the two preceding it. Each $T_i$ then wins $2$ and loses $2$ of those games. Every $T_i$ finishes with $1 + 2 = 3$ wins, $L$ finishes with $0$ , and the five teams are tied for the most wins.

The answer is $\boxed{\textbf{(D)}\ 5}$ .

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
Introduction to Counting & Probability, Chapter 4: Committees and Combinations