Difference between revisions of "2017 AMC 10A Problems/Problem 19"
Streamerbtw (talk | contribs) (→Solution 2) |
Megaboy6679 (talk | contribs) m (→Solution 1: Casework) |
||
(35 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Alice refuses to sit next to either Bob or | + | Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of <math>5</math> chairs under these conditions? |
<math> \textbf{(A)}\ 12\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 28\qquad\textbf{(D)}\ 32\qquad\textbf{(E)}\ 40</math> | <math> \textbf{(A)}\ 12\qquad\textbf{(B)}\ 16\qquad\textbf{(C)}\ 28\qquad\textbf{(D)}\ 32\qquad\textbf{(E)}\ 40</math> | ||
− | ==Solution 1== | + | ==Solution 1: Casework== |
− | + | Let Alice be A, Bob be B, Carla be C, Derek be D, and Eric be E. | |
We can split this problem up into two cases: | We can split this problem up into two cases: | ||
<math>\textbf{Case 1: }</math> A sits on an edge seat. | <math>\textbf{Case 1: }</math> A sits on an edge seat. | ||
− | + | Since B and C can't sit next to A, that must mean either D or E sits next to A. After we pick either D or E, then either B or C must sit next to D/E. Then, we can arrange the two remaining people in two ways. Since there are two different edge seats that A can sit in, there are a total of <math>2 \cdot 2 \cdot 2 \cdot 2 = 16</math>. | |
<math>\textbf{Case 2: }</math> A does not sit in an edge seat. | <math>\textbf{Case 2: }</math> A does not sit in an edge seat. | ||
− | + | Still, the only two people that can sit next to A are either D or E, and there are two ways to permute them, and this also handles the restriction that D can't sit next to E. Then, there are two ways to arrange B and C, the remaining people. However, there are three initial seats that A can sit in, so there are <math>3 \cdot 2 \cdot 2 = 12</math> seatings in this case. | |
− | Adding up all the | + | Adding up all the seatings, we have <math>16+12 = \boxed{\textbf{(C) } 28}</math>. |
==Solution 2== | ==Solution 2== | ||
− | Label the seats <math>1</math> through <math>5</math>. The number of ways to seat Derek and Eric in the five seats with no restrictions is <math>5 | + | Label the seats (from left to right) <math>1</math> through <math>5</math>. The number of ways to seat Derek and Eric in the five seats with no restrictions is <math>5 \cdot 4=20</math>. The number of ways to seat Derek and Eric such that they sit next to each other is <math>8</math> (we can treat Derek and Eric as a "block". There are four ways to seat this "block", and two ways to permute Derek and Eric, for a total of <math>4\cdot 2=8</math>), so the number of ways such that Derek and Eric don't sit next to each other is <math>20-8=12</math>. Note that once Derek and Eric are seated, we can divide into three cases. |
− | The first case is that they sit at each end. There are two ways to seat Derek and Eric. But this is impossible because then Alice, Bob, and Carla would have to sit in some order in the middle three seats which would lead to Alice sitting next to Bob or Carla, a contradiction. So this case gives us < | + | The first case is that they sit at each end. There are two ways to seat Derek and Eric. But this is impossible because then Alice, Bob, and Carla would have to sit in some order in the middle three seats which would lead to Alice sitting next to Bob or Carla, a contradiction. So this case gives us <math>0</math> ways. |
− | Another possible case is if Derek and Eric | + | Another possible case is if Derek and Eric sit in seats <math>2</math> and <math>4</math> in some order. There are <math>2</math> possible ways to seat Derek and Eric like this. This leaves Alice, Bob, and Carla to sit in any order in the remaining three seats. Since no two of these three seats are consecutive, there are <math>3!=6</math> ways to do this. So the second case gives us <math>2 \cdot 6=12</math> total ways. |
− | The last case is if once Derek and Eric are seated, exactly one pair of consecutive seats are available. There are < | + | The last case is if once Derek and Eric are seated, exactly one pair of consecutive seats are available. There are <math>12-2-2=8</math> ways to seat Derek and Eric like this. Once they are seated like this, Alice cannot sit in one of the two consecutive available seats without sitting next to Bob or Carla. So Alice has to sit in the other remaining chair. Then, there are two ways to seat Bob and Carla in the remaining two seats (which are consecutive). So this case gives us <math>8 \cdot 2=16</math> ways. |
− | So in total there are < | + | So in total there are <math>12+16=28</math> ways. Our answer is <math>\boxed{\textbf{(C)}\ 28}</math>. |
+ | <br> | ||
+ | Minor <math>\LaTeX</math> edits by fasterthanlight | ||
+ | |||
+ | Minor clarity edits by Carrot_Karen | ||
+ | |||
+ | ==Solution 3: PIE== | ||
+ | |||
+ | We start with complementary counting. After all, it's much easier to count the cases where some of these restraints are true, than when they aren't. | ||
+ | |||
+ | PIE: | ||
+ | Let's count the total number of cases where one of these is true: | ||
+ | |||
+ | When Alice is with Bob: | ||
+ | <math>2\cdot4!=48</math> | ||
+ | |||
+ | When Alice is with Carla: | ||
+ | <math>2\cdot4!=48</math> | ||
+ | |||
+ | When Derek is with Eric: | ||
+ | <math>2\cdot4!=48</math> | ||
+ | |||
+ | Then, we count the cases where two of these are true. | ||
+ | |||
+ | Alice is next to Carla, and Alice is also next to Bob. | ||
+ | There are two ways to rearrange Alice, Bob, and Carla so that this is true: | ||
+ | BAC and CAB. | ||
+ | <math>2\cdot3!=12</math> | ||
+ | |||
+ | Alice is next to Carla, and Derek is also next to Eric. | ||
+ | <math>2\cdot2\cdot3!=24</math> | ||
+ | |||
+ | Alice is next to Bob, and Derek is also next to Eric. | ||
+ | <math>2\cdot2\cdot3!=24</math> | ||
+ | |||
+ | Finally, we count the cases where all three of these are true: | ||
+ | <math>2\cdot2\cdot2=8</math> | ||
+ | |||
+ | We add up the cases where one of these are true: | ||
+ | <math>48\cdot3=144</math> | ||
+ | |||
+ | Subtract the cases where two of these are true: | ||
+ | <math>144-60=84</math> | ||
+ | |||
+ | And finally add back the cases where three of these are true: | ||
+ | <math>84+8=92</math> | ||
+ | |||
+ | Thus, our answer is <math>5!-92=28</math>, or <math>\boxed{\textbf{(C)} ~28}</math> | ||
+ | |||
+ | ~michaelchang1 | ||
+ | |||
+ | ~minor edit by lapisluminous | ||
+ | ty | ||
+ | |||
+ | ~minor clarity edits by hpotter2021 | ||
+ | |||
+ | ==Solution 4: Enumeration and casework of Alice's position== | ||
+ | To find the number of ways, we do casework. | ||
+ | |||
+ | Case 1: Alice sits in the first seat (leftmost) | ||
+ | Since Alice refuses to sit with Bob and Carla, then the seat on her immediate right must be Derek or Eric. The middle seat must be Bob or Carla (because Derek and Eric refuse to sit together). The seat to the right of the middle seat could be whoever is left over from Derek and Eric, or whoever is left together from Bob and Carla. The last seat only has one person left. There are <math>4</math> ways to permute Bob, Carla, Derek, and Eric, and <math>2</math> ways to pick who goes in the seat to the right of the middle seat, for <math>4\cdot2=8</math> seating arrangements here. | ||
+ | |||
+ | Case 2: Alice sits in the second seat | ||
+ | Derek and Eric must be on both sides of Alice because otherwise, we would have to put Bob or Carla next to Alice which is forbidden. Then Bob and Carla take the remaining two seats. There are <math>4</math> ways to permute and <math>4</math> arrangements here. | ||
+ | |||
+ | Case 3: Alice sits in the middle seat | ||
+ | Once again, Derek and Eric must be on both sides of Alice, and Bob and Carla need to take the two remaining seats. There are also <math>4</math> ways to permute and <math>4</math> arrangements here. | ||
+ | |||
+ | Case 4: Alice sits in the fourth seat | ||
+ | By symmetry, this is the same as case 2. There are <math>4</math> arrangements. | ||
+ | |||
+ | Case 5: Alice sits in the last seat (rightmost) | ||
+ | By symmetry, this is the same as case 1. There are <math>8</math> arrangements. | ||
+ | |||
+ | Adding up the cases, there are <math>8+4+4+4+8=28</math> total seating arrangements <math>\Longrightarrow \boxed{\textbf{(C) } 28}</math> | ||
+ | |||
+ | ~JH. L | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/5UojVH4Cqqs?t=2101 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==Video Solution== | ==Video Solution== |
Latest revision as of 01:31, 31 January 2023
Contents
Problem
Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of chairs under these conditions?
Solution 1: Casework
Let Alice be A, Bob be B, Carla be C, Derek be D, and Eric be E. We can split this problem up into two cases:
A sits on an edge seat.
Since B and C can't sit next to A, that must mean either D or E sits next to A. After we pick either D or E, then either B or C must sit next to D/E. Then, we can arrange the two remaining people in two ways. Since there are two different edge seats that A can sit in, there are a total of .
A does not sit in an edge seat.
Still, the only two people that can sit next to A are either D or E, and there are two ways to permute them, and this also handles the restriction that D can't sit next to E. Then, there are two ways to arrange B and C, the remaining people. However, there are three initial seats that A can sit in, so there are seatings in this case.
Adding up all the seatings, we have .
Solution 2
Label the seats (from left to right) through
. The number of ways to seat Derek and Eric in the five seats with no restrictions is
. The number of ways to seat Derek and Eric such that they sit next to each other is
(we can treat Derek and Eric as a "block". There are four ways to seat this "block", and two ways to permute Derek and Eric, for a total of
), so the number of ways such that Derek and Eric don't sit next to each other is
. Note that once Derek and Eric are seated, we can divide into three cases.
The first case is that they sit at each end. There are two ways to seat Derek and Eric. But this is impossible because then Alice, Bob, and Carla would have to sit in some order in the middle three seats which would lead to Alice sitting next to Bob or Carla, a contradiction. So this case gives us ways.
Another possible case is if Derek and Eric sit in seats and
in some order. There are
possible ways to seat Derek and Eric like this. This leaves Alice, Bob, and Carla to sit in any order in the remaining three seats. Since no two of these three seats are consecutive, there are
ways to do this. So the second case gives us
total ways.
The last case is if once Derek and Eric are seated, exactly one pair of consecutive seats are available. There are ways to seat Derek and Eric like this. Once they are seated like this, Alice cannot sit in one of the two consecutive available seats without sitting next to Bob or Carla. So Alice has to sit in the other remaining chair. Then, there are two ways to seat Bob and Carla in the remaining two seats (which are consecutive). So this case gives us
ways.
So in total there are ways. Our answer is
.
Minor edits by fasterthanlight
Minor clarity edits by Carrot_Karen
Solution 3: PIE
We start with complementary counting. After all, it's much easier to count the cases where some of these restraints are true, than when they aren't.
PIE: Let's count the total number of cases where one of these is true:
When Alice is with Bob:
When Alice is with Carla:
When Derek is with Eric:
Then, we count the cases where two of these are true.
Alice is next to Carla, and Alice is also next to Bob.
There are two ways to rearrange Alice, Bob, and Carla so that this is true:
BAC and CAB.
Alice is next to Carla, and Derek is also next to Eric.
Alice is next to Bob, and Derek is also next to Eric.
Finally, we count the cases where all three of these are true:
We add up the cases where one of these are true:
Subtract the cases where two of these are true:
And finally add back the cases where three of these are true:
Thus, our answer is , or
~michaelchang1
~minor edit by lapisluminous ty
~minor clarity edits by hpotter2021
Solution 4: Enumeration and casework of Alice's position
To find the number of ways, we do casework.
Case 1: Alice sits in the first seat (leftmost)
Since Alice refuses to sit with Bob and Carla, then the seat on her immediate right must be Derek or Eric. The middle seat must be Bob or Carla (because Derek and Eric refuse to sit together). The seat to the right of the middle seat could be whoever is left over from Derek and Eric, or whoever is left together from Bob and Carla. The last seat only has one person left. There are ways to permute Bob, Carla, Derek, and Eric, and
ways to pick who goes in the seat to the right of the middle seat, for
seating arrangements here.
Case 2: Alice sits in the second seat
Derek and Eric must be on both sides of Alice because otherwise, we would have to put Bob or Carla next to Alice which is forbidden. Then Bob and Carla take the remaining two seats. There are ways to permute and
arrangements here.
Case 3: Alice sits in the middle seat
Once again, Derek and Eric must be on both sides of Alice, and Bob and Carla need to take the two remaining seats. There are also ways to permute and
arrangements here.
Case 4: Alice sits in the fourth seat
By symmetry, this is the same as case 2. There are arrangements.
Case 5: Alice sits in the last seat (rightmost)
By symmetry, this is the same as case 1. There are arrangements.
Adding up the cases, there are total seating arrangements
~JH. L
Video Solution by OmegaLearn
https://youtu.be/5UojVH4Cqqs?t=2101
~ pi_is_3.14
Video Solution
See Also
2017 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 18 |
Followed by Problem 20 | |
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 |
2017 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 13 |
Followed by Problem 15 |
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.