Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 AMC 10B Problems/Problem 22"

m (→‎Problem)
 
(31 intermediate revisions by 19 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
A set of teams held a round-robn tournament in which every team played every other team exactly once. Every team won <math>10</math> games and lost <math>10</math> games; there were no ties. How many sets of three teams <math>\{A, B, C\}</math> were there in which <math>A</math> beat <math>B</math>, <math>B</math> beat <math>C</math>, and <math>C</math> beat <math>A?</math>
+
A set of teams held a round-robin tournament in which every team played every other team exactly once. Every team won <math>10</math> games and lost <math>10</math> games; there were no ties. How many sets of three teams <math>\{A, B, C\}</math> were there in which <math>A</math> beat <math>B</math>, <math>B</math> beat <math>C</math>, and <math>C</math> beat <math>A?</math>
  
 
<math>\textbf{(A)}\ 385 \qquad
 
<math>\textbf{(A)}\ 385 \qquad
Line 9: Line 9:
 
\textbf{(E)}\ 1330</math>
 
\textbf{(E)}\ 1330</math>
  
−
==Solution==
+
==Solution 1==
−
There are <math>21</math> teams. Any of the <math>\tbinom{21}3=1330</math> sets of three teams must either be a fork (in which one team beat both the others) or a cycle:
+
There are <math>10 \cdot 2+1=21</math> teams. Any of the <math>\tbinom{21}3=1330</math> sets of three teams must either be a fork (in which one team beat both the others) or a cycle:
  
−
<asy>size(7cm);label("X",(5,5));label("Z",(10,0));label("Y",(0,0));draw((4,4)--(1,1),EndArrow);draw((6,4)--(9,1),EndArrow);
+
<asy>size(7cm);label("A",(5,5));label("C",(10,0));label("B",(0,0));draw((4,4)--(1,1),EndArrow);draw((6,4)--(9,1),EndArrow);
−
label("X",(20,5));label("Z",(25,0));label("Y",(15,0));draw((19,4)--(16,1),EndArrow);draw((16,0)--(24,0),EndArrow);draw((24,1)--(21,4),EndArrow);
+
label("A",(20,5));label("C",(25,0));label("B",(15,0));draw((19,4)--(16,1),EndArrow);draw((16,0)--(24,0),EndArrow);draw((24,1)--(21,4),EndArrow);
 
</asy>
 
</asy>
−
But we know that every team beat exactly <math>10</math> other teams, so for each possible <math>X</math> at the head of a fork, there are always exactly <math>\tbinom{10}2</math> choices for <math>Y</math> and <math>Z</math>. Therefore there are <math>21\cdot\tbinom{10}2=945</math> forks, and all the rest must be cycles.
+
But we know that every team beat exactly <math>10</math> other teams, so for each possible <math>A</math> at the head of a fork, there are always exactly <math>\tbinom{10}2</math> choices for <math>B</math> and <math>C</math> as <math>A</math> beat exactly 10 teams and we are choosing 2 of them. Therefore there are <math>21\cdot\tbinom{10}2=945</math> forks, and all the rest must be cycles.
  
−
Thus the answer is <math>1330-945=385</math> which is <math>\textbf{(A)}</math>.
+
Thus the answer is <math>1330-945=385</math> which is <math>\boxed{\textbf{(A)}}</math>.
 +
 
 +
==Solution 2 (Cheap Solution)==
 +
Since there are <math>21</math> teams and for each set of three teams there is a cycle, there are a total of <math>\tbinom{21}3=1330</math> cycles of three teams.  Because about <math>1/4</math> of the cycles <math>\{A, B, C\}</math> satisfy the conditions of the problems, our answer is close to <math>1/4 \cdot 1330=332.5</math>. Looking at the answer choices, we find that <math>332.5</math> is closer to <math>385</math> than any other answer choices, and that the next closest is <math>665</math> which is twice of <math>332.5</math>, so our answer is <math>385</math> which is <math>\boxed{\textbf{(A)}}</math>.
 +
 
 +
 
 +
Speaking of cheap solutions, you can let the teams be <math>1,2,3,..21</math> and have <math>i</math> beat <math>i+1,i+2, ... i+10 \pmod{21}</math> and lose to <math>i+11,i+12, ... i+20 \pmod{21}.</math> You can choose any random team as <math>A</math> for <math>21</math> ways but overcount since set, so divide by <math>3</math> so multiply by <math>7.</math> Now we can proceed w/casework (which isn't too hard). Eventually you realize the sum is <math>7(1+2+\cdots+10) = \boxed{\textbf{(A)}}</math>.
 +
 
 +
==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 <math>3</math> 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 <math>10</math> 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 <math>A</math>, is at position <math>0</math> out of <math>20</math> on the circle.
 +
 
 +
If team <math>A</math> is to beat team <math>B</math>, since we are assuming each team beats the 10 members clockwise of themselves, there are <math>10</math> places on the circle that team <math>B</math> could be: positions <math>1</math> through <math>10</math>. Also, if team <math>C</math> is to beat team <math>A</math>, team <math>C</math> must be located from positions <math>11</math> to <math>20</math>.
 +
 
 +
If Team <math>B</math> is in position <math>n</math>, <math>C</math> must be located from position <math>n+1</math> to position <math>n+10</math>, since <math>B</math> beats <math>C</math>. We also just found that <math>C</math>'s position must be between <math>11</math> and <math>20</math> inclusive. So, when <math>B</math> is in position <math>1</math>, <math>C</math> can only be in position <math>11</math>. When <math>B</math> is in position <math>2</math>, <math>C</math> can be in position <math>11</math> or <math>12</math>. In general, when <math>B</math> is in position <math>n</math>, there are <math>n</math> choices for where <math>C</math> can be. So, there are <math>1+2+3+ \dots + 10 = 55</math> ways to place <math>B</math> and <math>C</math>. There are <math>21</math> players to choose as player <math>A</math>, and each working set will be counted <math>3</math> times, so our final answer is <math>55 \cdot 21 \div 3 = \boxed{385, \textbf{(A)}}</math>.
 +
 
 +
==Solution 4 (Aggregate Counting)==
 +
 
 +
This is a Graph Theory problem with directed graph. There are <math>21</math> teams in total. WLOG, pick team <math>A</math>, there are <math>10</math> teams that lost to <math>A</math> and <math>10</math> teams that won over <math>A</math>. Call the group of teams that lost to <math>A</math> group <math>L</math>, and the group of teams that won over <math>A</math> group <math>W</math>.
 +
 
 +
<asy>
 +
size(7cm);
 +
label("A",(20,5));
 +
label("Group W",(27,0));
 +
label("Group L",(13,0));
 +
draw((19,4)--(16,1),EndArrow);
 +
draw((16,0)--(24,0),EndArrow);
 +
draw((24,1)--(21,4),EndArrow);
 +
</asy>
 +
 
 +
Any team from group <math>L</math> that won a team from group <math>W</math> will form a cycle with <math>A</math>. Now we need to count how many teams in group <math>L</math> won over a team from group <math>W</math>. The total number of wins in group <math>L</math> is <math>10 \cdot 10 =100</math>. There are <math>\tbinom{10}2=45</math> wins among the teams inside group <math>L</math>. So group <math>L</math> has <math>100-45=55</math> wins over group <math>W</math>.
 +
 
 +
<cmath>\frac{21 \cdot 55}{3}=\boxed{385, \textbf{(A)}}</cmath>
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen]
 +
 
 +
== Video Solution by Pi Academy ==
 +
https://youtu.be/PeO-o9MOIYo?si=ZipIxXwzJPeTaEAP
 +
 
 +
~ Pi Academy
 +
 
 +
[[Category:Introductory_Combinatorics_Problems]]
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2016|ab=B|num-b=21|num-a=23}}
 
{{AMC10 box|year=2016|ab=B|num-b=21|num-a=23}}
 +
{{AMC12 box|year=2016|ab=B|num-b=19|num-a=21}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 18:54, 8 October 2024

Problem

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?$

$\textbf{(A)}\ 385 \qquad \textbf{(B)}\ 665 \qquad \textbf{(C)}\ 945 \qquad \textbf{(D)}\ 1140 \qquad \textbf{(E)}\ 1330$

Solution 1

There are $10 \cdot 2+1=21$ teams. Any of the $\tbinom{21}3=1330$ sets of three teams must either be a fork (in which one team beat both the others) or a cycle:

[asy]size(7cm);label("A",(5,5));label("C",(10,0));label("B",(0,0));draw((4,4)--(1,1),EndArrow);draw((6,4)--(9,1),EndArrow); label("A",(20,5));label("C",(25,0));label("B",(15,0));draw((19,4)--(16,1),EndArrow);draw((16,0)--(24,0),EndArrow);draw((24,1)--(21,4),EndArrow); [/asy] But we know that every team beat exactly $10$ other teams, so for each possible $A$ at the head of a fork, there are always exactly $\tbinom{10}2$ choices for $B$ and $C$ as $A$ beat exactly 10 teams and we are choosing 2 of them. Therefore there are $21\cdot\tbinom{10}2=945$ forks, and all the rest must be cycles.

Thus the answer is $1330-945=385$ which is $\boxed{\textbf{(A)}}$.

Solution 2 (Cheap Solution)

Since there are $21$ teams and for each set of three teams there is a cycle, there are a total of $\tbinom{21}3=1330$ cycles of three teams. Because about $1/4$ of the cycles $\{A, B, C\}$ satisfy the conditions of the problems, our answer is close to $1/4 \cdot 1330=332.5$. Looking at the answer choices, we find that $332.5$ is closer to $385$ than any other answer choices, and that the next closest is $665$ which is twice of $332.5$, so our answer is $385$ which is $\boxed{\textbf{(A)}}$.


Speaking of cheap solutions, you can let the teams be $1,2,3,..21$ and have $i$ beat $i+1,i+2, ... i+10 \pmod{21}$ and lose to $i+11,i+12, ... i+20 \pmod{21}.$ You can choose any random team as $A$ for $21$ ways but overcount since set, so divide by $3$ so multiply by $7.$ Now we can proceed w/casework (which isn't too hard). Eventually you realize the sum is $7(1+2+\cdots+10) = \boxed{\textbf{(A)}}$.

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 $3$ 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 $10$ 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 $A$, is at position $0$ out of $20$ on the circle.

If team $A$ is to beat team $B$, since we are assuming each team beats the 10 members clockwise of themselves, there are $10$ places on the circle that team $B$ could be: positions $1$ through $10$. Also, if team $C$ is to beat team $A$, team $C$ must be located from positions $11$ to $20$.

If Team $B$ is in position $n$, $C$ must be located from position $n+1$ to position $n+10$, since $B$ beats $C$. We also just found that $C$'s position must be between $11$ and $20$ inclusive. So, when $B$ is in position $1$, $C$ can only be in position $11$. When $B$ is in position $2$, $C$ can be in position $11$ or $12$. In general, when $B$ is in position $n$, there are $n$ choices for where $C$ can be. So, there are $1+2+3+ \dots + 10 = 55$ ways to place $B$ and $C$. There are $21$ players to choose as player $A$, and each working set will be counted $3$ times, so our final answer is $55 \cdot 21 \div 3 = \boxed{385, \textbf{(A)}}$.

Solution 4 (Aggregate Counting)

This is a Graph Theory problem with directed graph. There are $21$ teams in total. WLOG, pick team $A$, there are $10$ teams that lost to $A$ and $10$ teams that won over $A$. Call the group of teams that lost to $A$ group $L$, and the group of teams that won over $A$ group $W$.

[asy] size(7cm); label("A",(20,5)); label("Group W",(27,0)); label("Group L",(13,0)); draw((19,4)--(16,1),EndArrow); draw((16,0)--(24,0),EndArrow); draw((24,1)--(21,4),EndArrow); [/asy]

Any team from group $L$ that won a team from group $W$ will form a cycle with $A$. Now we need to count how many teams in group $L$ won over a team from group $W$. The total number of wins in group $L$ is $10 \cdot 10 =100$. There are $\tbinom{10}2=45$ wins among the teams inside group $L$. So group $L$ has $100-45=55$ wins over group $W$.

\[\frac{21 \cdot 55}{3}=\boxed{385, \textbf{(A)}}\]

~isabelchen

Video Solution by Pi Academy

https://youtu.be/PeO-o9MOIYo?si=ZipIxXwzJPeTaEAP

~ Pi Academy

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
2016 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 19 		Followed by
Problem 21
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 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AMC_10B_Problems/Problem_22&oldid=229321"