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 "2012 AMC 12B Problems/Problem 16"
 
(55 intermediate revisions by 29 users not shown)
Line 6: Line 6:
 
<math> \textbf{(A)}\ 108\qquad\textbf{(B)}\ 132\qquad\textbf{(C)}\ 671\qquad\textbf{(D)}\ 846\qquad\textbf{(E)}\ 1105 </math>
 
<math> \textbf{(A)}\ 108\qquad\textbf{(B)}\ 132\qquad\textbf{(C)}\ 671\qquad\textbf{(D)}\ 846\qquad\textbf{(E)}\ 1105 </math>
  
 +
==Solutions==
  
 +
=== Solution 1===
 +
Let the ordered triple <math>(a,b,c)</math> denote that <math>a</math> songs are liked by Amy and Beth, <math>b</math> songs by Beth and Jo, and <math>c</math> songs by Jo and Amy. The only possible triples are <math>(1,1,1), (2,1,1), (1,2,1)(1,1,2)</math>.
  
 +
To show this, first observe these are all valid conditions. Second, note that none of <math>a,b,c</math> can be bigger than 3. Suppose otherwise, that <math>a = 3</math>. Without loss of generality, say that Amy and Beth like songs 1, 2, and 3. Then because there is at least one song liked by each pair of girls, we require either <math>b</math> or <math>c</math> to be at least 1. In fact, we require either <math>b</math> or <math>c</math> to equal 1, otherwise there will be a song liked by all three. Suppose <math>b = 1</math>. Then we must have <math>c=0</math> since no song is liked by all three girls, which contradicts with the statement "for each of the three pairs of the girls, there is at least one song liked by those two girls".
  
 +
'''Case 1''': How many ways are there for <math>(a,b,c)</math> to equal <math>(1,1,1)</math>? There are 4 choices for which song is liked by Amy and Beth, 3 choices for which song is liked by Beth and Jo, and 2 choices for which song is liked by Jo and Amy. The fourth song can be liked by only one of the girls, or none of the girls, for a total of 4 choices. So <math>(a,b,c)=(1,1,1)</math> in <math>4\cdot3\cdot2\cdot4 = 96</math> ways.
  
−
== Solution==
+
'''Case 2''': To find the number of ways for <math>(a,b,c) = (2,1,1)</math> (without order), observe there are <math>\binom{4}{2} = 6</math> choices of songs for the first pair of girls. There remain 2 choices of songs for the next pair (who only like one song). The last song is given to the last pair of girls. But observe that we can let any three pairs of the girls to like two songs, so we multiply by 3. In this case there are <math>(6\cdot2)\cdot3=36</math> ways for the girls to like the songs.
−
Let the ordered triple <math>(a,b,c)</math> denote that <math>a</math> songs are liked by Amy and Beth, <math>b</math> songs by Beth and Jo, and <math>c</math> songs by Jo and Amy. We claim that the only possible triples are <math>(1,1,1), (2,1,1), (1,2,1)(1,1,2)</math>.  
 
  
−
To show this, observe these are all valid conditions. Second, note that none of <math>a,b,c</math> can be bigger than 3. Suppose otherwise, that <math>a = 3</math>. Without loss of generality, say that Amy and Beth like songs 1, 2, and 3. Then because there is at least one song liked by each pair of girls, we require either <math>b</math> or <math>c</math> to be at least 1. In fact, we require either <math>b</math> or <math>c</math> to equal 1, otherwise there will be a song liked by all three. Suppose <math>b = 1</math>. Then we must have <math>c=0</math> since no song is liked by all three girls, a contradiction.
+
That gives a total of <math>96 + 36 = 132</math> ways for the girls to like the songs, so the answer is <math>\boxed{(\textrm{\textbf{B}})}</math>.
  
−
'''Case 1''':How many ways are there for <math>(a,b,c)</math> to equal <math>(1,1,1)</math>? There are 4 choices for which song is liked by Amy and Beth, 3 choices for which song is liked by Beth and Jo, and 2 choices for which song is liked by Jo and Amy. The fourth song can be liked by only one of the girls, or none of the girls, for a total of 4 choices. So <math>(a,b,c)=(1,1,1)</math> in <math>4\cdot3\cdot2\cdot4 = 96</math> ways.
+
=== Solution 2===
  
−
'''Case 2''':To find the number of ways for <math>(a,b,c) = (2,1,1)</math>, observe there are <math>\binom{4}{2} = 6</math> choices of songs for the first pair of girls. There remain 2 choices of songs for the next pair (who only like one song). The last song is given to the last pair of girls. But observe that we let any three pairs of the girls like two songs, so we multiply by 3. In this case there are <math>6\cdot2\cdot3=36</math> ways for the girls to like the songs.
 
  
−
That gives a total of <math>96 + 36 = \boxed{132}</math> ways for the girls to like the song, so the answer is <math>(\textrm{\textbf{B}})</math>.
+
Let <math>AB, BJ</math>, and <math>AJ</math> denote a song that is liked by Amy and Beth (but not Jo), Beth and Jo (but not Amy), and Amy and Jo (but not Beth), respectively. Similarly, let <math>A, B, J,</math> and <math>N</math> denote a song that is liked by only Amy, only Beth, only Jo, and none of them, respectively. Since we know that there is at least <math>1\: AB, BJ</math>, and <math>AJ</math>, they must be <math>3</math> songs out of the <math>4</math> that Amy, Beth, and Jo listened to. The fourth song can be of any type <math>N, A, B, J, AB, BJ</math>, and <math>AJ</math> (there is no <math>ABJ</math> because no song is liked by all three, as stated in the problem.) Therefore, we must find the number of ways to rearrange <math>AB, BJ, AJ</math>, and a song from the set <math>\{N, A, B, J, AB, BJ, AJ\}</math>.
 +
 
 +
Case 1: Fourth song = <math>N, A, B, J </math>
 +
 
 +
Note that in Case 1, all four of the choices for the fourth song are different from the first three songs.
 +
 
 +
Number of ways to rearrange = <math>(4!)</math> rearrangements for each choice <math>*\: 4</math> choices = <math>96</math>.
 +
 
 +
Case 2: Fourth song = <math>AB, BJ, AJ</math>
 +
 
 +
Note that in Case <math>2</math>, all three of the choices for the fourth song repeat somewhere in the first three songs.
 +
 
 +
Number of ways to rearrange = <math>(4!/2!)</math> rearrangements for each choice <math>*\: 3</math> choices = <math>36</math>.
 +
 
 +
<math>96 + 36 = \boxed{\textbf{(B)} \: 132}</math>.
 +
 
 +
=== Solution 3===
 +
 
 +
 
 +
There are <math>\binom{4}{3}</math> ways to choose the three songs that are liked by the three pairs of girls.
 +
 
 +
There are <math>3!</math> ways to determine how the three songs are liked, or which song is liked by which pair of girls.
 +
 
 +
In total, there are <math>\binom{4}{3}\cdot3!</math> possibilities for the first <math>3</math> songs.
 +
 
 +
There are <math>3</math> cases for the 4th song, call it song D.
 +
 
 +
Case <math>1</math>: D is disliked by all <math>3</math> girls <math>\implies</math> there is only <math>1</math> possibility.
 +
 
 +
Case <math>2</math>: D is liked by exactly <math>1</math> girl <math>\implies</math> there are <math>3</math> possibility.
 +
 
 +
Case <math>3</math>: D is liked by exactly <math>2</math> girls <math>\implies</math> there are <math>3</math> pairs of girls to choose from. However, there's overlap when the other song liked by the same pair of girl is counted as the 4th song at some point, in which case D would be counted as one of the first <math>3</math> songs liked by the same girls.
 +
 
 +
Counting the overlaps, there are <math>3</math> ways to choose the pair with overlaps and <math>4\cdot3=12</math> ways to choose what the other <math>2</math> pairs like independently. In total, there are <math>3\cdot12=36</math> overlapped possibilities.
 +
 
 +
Finally, there are <math>\binom{4}{3}\cdot3!\cdot(3+1+3)-36=132</math> ways for the songs to be likely by the girls. <math>\boxed{\mathrm{(B)}}</math>
 +
 
 +
~ Nafer
 +
 
 +
===Solution 4===
 +
This is a bipartite graph problem, with the girls as left vertices and songs as right vertices. An edge connecting left vertex and right vertex means that a girl likes a song.
 +
 
 +
Condition 1: "No song is liked by all three", means that the degree of right vertices is at most 2.
 +
 
 +
Condition 2: "for each of the three pairs of the girls, there is at least one song liked by those two girls but disliked by the third", means that for any pair of left vertices, there is at least a right vertex connecting to them.
 +
 
 +
To meet condition 2, there are at least 3 right vertices with 2 edges connecting to left vertices.  There are 2 cases:
 +
 
 +
Case 1: there are only 3 such right vertices. There are <math>\binom{4}{3}</math> such vertices, with <math>3!</math> ways of connections to the left vertices, total arrangements are <math>\binom{4}{3}\cdot3! = 24</math>. The fourth right vertex either has no edge to the 3 left vertices, or 1 edge to 1 of the 3 left vertices.  So there are <math>24\cdot(1+3) = 96</math> ways.
 +
 
 +
Case 2: there are 4 such right vertices, 2 of them have edges to the same pair of left vertices.  There are <math>\binom{4}{2}</math> such vertices, with <math>3!</math> ways of connections.  So there are <math>\binom{4}{2}\cdot3! = 36</math> ways.
 +
 
 +
Total ways are <math>96+36=132</math>.
 +
 
 +
Another way is to overcount then subtract overlap ways.  Similar to previous case 1,  the fourth right vertex could have all possible connection to the left vertices except connecting to all 3, so it is <math>2^3-1=7</math> ways, so the total ways are <math>\binom{4}{3}\cdot3!\cdot7 = 24\cdot7 = 168</math>.  But this overcounts the case 2 with 36 ways.  So total ways are <math>168-36=132</math>.
 +
 
 +
-[https://artofproblemsolving.com/wiki/index.php/User:Junche junche]
 +
 
 +
===Solution 5===
 +
 
 +
Let's assign to each of the 3 pairs a song that they like, and that song is disliked by the other girl(satisfy the problem's 2nd condition). The first pair has 4 choice, 2nd has 3 choice, and last one has 2 choice. <math>4 \cdot 3 \cdot 2</math>. Then the last song can be liked/disliked freely, so there is <math>2^3 = 8</math> total ways they can like/dislike the songs. Of these 8 cases, one of them is when they all like the song (which isn't allowed by the problem), so we subtract it away to have 7 cases. <math>4 \cdot 3 \cdot 2 \cdot 7 = 168</math>. But, we have overcounts when one pair of girls likes 2 songs, and the other girl dislikes those 2 songs. We can find the amount of cases that this happens by giving 1 pair of girls 2 songs that they like (and the other dislikes), and the other 2 pairs of girls 1 song that they like. There are 3 pairs of girls that we can choose to like 2 songs, so there are <math>3 \cdot \left(\binom {4}{2} \cdot 2 \cdot 1\right) = 36</math> ways. <math>168 - 36 = \boxed {\textbf{(B) 132}}</math>.
 +
 
 +
~heheman
 +
~Arcticturn (minor fixes in LaTeX)
 +
~EthanSpoon (minor fixes in LaTeX)
 +
 
 +
==Video Solution by Pi Academy==
 +
https://youtu.be/yZmJ-TEfiWI?si=fp2Jk-Y2VjtHr9RE ~ Pi Academy
 +
 
 +
==Video Solution by Richard Rusczyk==
 +
https://artofproblemsolving.com/videos/amc/2012amc10b/272
 +
 
 +
-dolphin7
 +
 
 +
 
 +
== See Also ==
 +
 
 +
 
 +
{{AMC10 box|year=2012|ab=B|num-b=23|num-a=25}}
 +
 
 +
{{AMC12 box|year=2012|ab=B|num-b=15|num-a=17}}
 +
 
 +
[[Category:Introductory Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 19:36, 6 October 2024

The following problem is from both the 2012 AMC 12B #16 and 2012 AMC 10B #24, so both problems redirect to this page.

Problem

Amy, Beth, and Jo listen to four different songs and discuss which ones they like. No song is liked by all three. Furthermore, for each of the three pairs of the girls, there is at least one song liked by those two girls but disliked by the third. In how many different ways is this possible?

$\textbf{(A)}\ 108\qquad\textbf{(B)}\ 132\qquad\textbf{(C)}\ 671\qquad\textbf{(D)}\ 846\qquad\textbf{(E)}\ 1105$

Solutions

Solution 1

Let the ordered triple $(a,b,c)$ denote that $a$ songs are liked by Amy and Beth, $b$ songs by Beth and Jo, and $c$ songs by Jo and Amy. The only possible triples are $(1,1,1), (2,1,1), (1,2,1)(1,1,2)$.

To show this, first observe these are all valid conditions. Second, note that none of $a,b,c$ can be bigger than 3. Suppose otherwise, that $a = 3$. Without loss of generality, say that Amy and Beth like songs 1, 2, and 3. Then because there is at least one song liked by each pair of girls, we require either $b$ or $c$ to be at least 1. In fact, we require either $b$ or $c$ to equal 1, otherwise there will be a song liked by all three. Suppose $b = 1$. Then we must have $c=0$ since no song is liked by all three girls, which contradicts with the statement "for each of the three pairs of the girls, there is at least one song liked by those two girls".

Case 1: How many ways are there for $(a,b,c)$ to equal $(1,1,1)$? There are 4 choices for which song is liked by Amy and Beth, 3 choices for which song is liked by Beth and Jo, and 2 choices for which song is liked by Jo and Amy. The fourth song can be liked by only one of the girls, or none of the girls, for a total of 4 choices. So $(a,b,c)=(1,1,1)$ in $4\cdot3\cdot2\cdot4 = 96$ ways.

Case 2: To find the number of ways for $(a,b,c) = (2,1,1)$ (without order), observe there are $\binom{4}{2} = 6$ choices of songs for the first pair of girls. There remain 2 choices of songs for the next pair (who only like one song). The last song is given to the last pair of girls. But observe that we can let any three pairs of the girls to like two songs, so we multiply by 3. In this case there are $(6\cdot2)\cdot3=36$ ways for the girls to like the songs.

That gives a total of $96 + 36 = 132$ ways for the girls to like the songs, so the answer is $\boxed{(\textrm{\textbf{B}})}$.

Solution 2

Let $AB, BJ$, and $AJ$ denote a song that is liked by Amy and Beth (but not Jo), Beth and Jo (but not Amy), and Amy and Jo (but not Beth), respectively. Similarly, let $A, B, J,$ and $N$ denote a song that is liked by only Amy, only Beth, only Jo, and none of them, respectively. Since we know that there is at least $1\: AB, BJ$, and $AJ$, they must be $3$ songs out of the $4$ that Amy, Beth, and Jo listened to. The fourth song can be of any type $N, A, B, J, AB, BJ$, and $AJ$ (there is no $ABJ$ because no song is liked by all three, as stated in the problem.) Therefore, we must find the number of ways to rearrange $AB, BJ, AJ$, and a song from the set $\{N, A, B, J, AB, BJ, AJ\}$.

Case 1: Fourth song = $N, A, B, J$

Note that in Case 1, all four of the choices for the fourth song are different from the first three songs.

Number of ways to rearrange = $(4!)$ rearrangements for each choice $*\: 4$ choices = $96$.

Case 2: Fourth song = $AB, BJ, AJ$

Note that in Case $2$, all three of the choices for the fourth song repeat somewhere in the first three songs.

Number of ways to rearrange = $(4!/2!)$ rearrangements for each choice $*\: 3$ choices = $36$.

$96 + 36 = \boxed{\textbf{(B)} \: 132}$.

Solution 3

There are $\binom{4}{3}$ ways to choose the three songs that are liked by the three pairs of girls.

There are $3!$ ways to determine how the three songs are liked, or which song is liked by which pair of girls.

In total, there are $\binom{4}{3}\cdot3!$ possibilities for the first $3$ songs.

There are $3$ cases for the 4th song, call it song D.

Case $1$: D is disliked by all $3$ girls $\implies$ there is only $1$ possibility.

Case $2$: D is liked by exactly $1$ girl $\implies$ there are $3$ possibility.

Case $3$: D is liked by exactly $2$ girls $\implies$ there are $3$ pairs of girls to choose from. However, there's overlap when the other song liked by the same pair of girl is counted as the 4th song at some point, in which case D would be counted as one of the first $3$ songs liked by the same girls.

Counting the overlaps, there are $3$ ways to choose the pair with overlaps and $4\cdot3=12$ ways to choose what the other $2$ pairs like independently. In total, there are $3\cdot12=36$ overlapped possibilities.

Finally, there are $\binom{4}{3}\cdot3!\cdot(3+1+3)-36=132$ ways for the songs to be likely by the girls. $\boxed{\mathrm{(B)}}$

~ Nafer

Solution 4

This is a bipartite graph problem, with the girls as left vertices and songs as right vertices. An edge connecting left vertex and right vertex means that a girl likes a song.

Condition 1: "No song is liked by all three", means that the degree of right vertices is at most 2.

Condition 2: "for each of the three pairs of the girls, there is at least one song liked by those two girls but disliked by the third", means that for any pair of left vertices, there is at least a right vertex connecting to them.

To meet condition 2, there are at least 3 right vertices with 2 edges connecting to left vertices. There are 2 cases:

Case 1: there are only 3 such right vertices. There are $\binom{4}{3}$ such vertices, with $3!$ ways of connections to the left vertices, total arrangements are $\binom{4}{3}\cdot3! = 24$. The fourth right vertex either has no edge to the 3 left vertices, or 1 edge to 1 of the 3 left vertices. So there are $24\cdot(1+3) = 96$ ways.

Case 2: there are 4 such right vertices, 2 of them have edges to the same pair of left vertices. There are $\binom{4}{2}$ such vertices, with $3!$ ways of connections. So there are $\binom{4}{2}\cdot3! = 36$ ways.

Total ways are $96+36=132$.

Another way is to overcount then subtract overlap ways. Similar to previous case 1, the fourth right vertex could have all possible connection to the left vertices except connecting to all 3, so it is $2^3-1=7$ ways, so the total ways are $\binom{4}{3}\cdot3!\cdot7 = 24\cdot7 = 168$. But this overcounts the case 2 with 36 ways. So total ways are $168-36=132$.

-junche

Solution 5

Let's assign to each of the 3 pairs a song that they like, and that song is disliked by the other girl(satisfy the problem's 2nd condition). The first pair has 4 choice, 2nd has 3 choice, and last one has 2 choice. $4 \cdot 3 \cdot 2$. Then the last song can be liked/disliked freely, so there is $2^3 = 8$ total ways they can like/dislike the songs. Of these 8 cases, one of them is when they all like the song (which isn't allowed by the problem), so we subtract it away to have 7 cases. $4 \cdot 3 \cdot 2 \cdot 7 = 168$. But, we have overcounts when one pair of girls likes 2 songs, and the other girl dislikes those 2 songs. We can find the amount of cases that this happens by giving 1 pair of girls 2 songs that they like (and the other dislikes), and the other 2 pairs of girls 1 song that they like. There are 3 pairs of girls that we can choose to like 2 songs, so there are $3 \cdot \left(\binom {4}{2} \cdot 2 \cdot 1\right) = 36$ ways. $168 - 36 = \boxed {\textbf{(B) 132}}$.

~heheman ~Arcticturn (minor fixes in LaTeX) ~EthanSpoon (minor fixes in LaTeX)

Video Solution by Pi Academy

https://youtu.be/yZmJ-TEfiWI?si=fp2Jk-Y2VjtHr9RE ~ Pi Academy

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012amc10b/272

-dolphin7


See Also

2012 AMC 10B (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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
2012 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 15 		Followed by
Problem 17
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=2012_AMC_12B_Problems/Problem_16&oldid=229169"