2016 AMC 10B Problems/Problem 22
Contents
Problem
A set of teams held a round-robin tournament in which every team played every other team exactly once. Every team won games and lost
games; there were no ties. How many sets of three teams
were there in which
beat
,
beat
, and
beat
Solution 1
There are teams. Any of the
sets of three teams must either be a fork (in which one team beat both the others) or a cycle:
But we know that every team beat exactly
other teams, so for each possible
at the head of a fork, there are always exactly
choices for
and
as
beat exactly 10 teams and we are choosing 2 of them. Therefore there are
forks, and all the rest must be cycles.
Thus the answer is which is
.
Solution 2 (Cheap Solution)
Since there are teams and for each set of three teams there is a cycle, there are a total of
cycles of three teams. Because about
of the cycles
satisfy the conditions of the problems, our answer is close to
. Looking at the answer choices, we find that
is closer to
than any other answer choices, and that the next closest is
which is twice of
, so our answer is
which is
.
Speaking of cheap solutions, you can let the teams be and have
beat
and lose to
You can choose any random team as
for
ways but overcount since set, so divide by
so multiply by
Now we can proceed w/casework (which isn't too hard). Eventually you realize the sum is
.
Solution 3 (Circle)
Let's arrange all the teams in a circle and assume that each team won against the first 10 teams clockwise of themselves, and lost against the first 10 teams counter-clockwise of themselves.
Consider a working set of teams: moving clockwise, we know that the first team beat the team clockwise of itself, that team beat the next team clockwise of itself, and the final team beat the first team, which would be clockwise of itself. However, we also must remember that if the first team beat the second team, moving clockwise, the second team cannot be more than
teams away from the first team; the same applies to the second and third team, and the third and first team.
Let's say, WLOG, that the first team, team , is at position
out of
on the circle.
If team is to beat team
, since we are assuming each team beats the 10 members clockwise of themselves, there are
places on the circle that team
could be: positions
through
. Also, if team
is to beat team
, team
must be located from positions
to
.
If Team is in position
,
must be located from position
to position
, since
beats
. We also just found that
's position must be between
and
inclusive. So, when
is in position
,
can only be in position
. When
is in position
,
can be in position
or
. In general, when
is in position
, there are
choices for where
can be. So, there are
ways to place
and
. There are
players to choose as player
, and each working set will be counted
times, so our final answer is
.
Solution 4 (Aggregate Counting)
This is a Graph Theory problem with directed graph. There are teams in total. WLOG, pick team
, there are
teams that lost to
and
teams that won over
. Call the group of teams that lost to
group
, and the group of teams that won over
group
.
Any team from group that won a team from group
will form a cycle with
. Now we need to count how many teams in group
won over a team from group
. The total number of wins in group
is
. There are
wins among the teams inside group
. So group
has
wins over group
.
~isabelchen
See Also
2016 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.