Difference between revisions of "2020 AIME II Problems/Problem 9"

(Problem)
(19 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.
 
While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.
 +
 +
==Solution (Bash)==
 +
There are <math>2^{5}-1</math> intersections that we must consider if we are to perform a PIE bash on this problem. Since we don't really want to think that hard, and bashing does not take that long for this problem, we can write down half of all permutations that satisfy the conditions presented in the problem in "lexicographically next" order to keep track easily. We do this for all cases such that the first "person" is <math>A-C</math>, and multiply by two, since the number of working permutations with <math>D-F</math> as the first person is the same as if it were <math>A-C</math>, hence, after doing such a bash, we get <math>45\times2=90</math> permutations that result in no consecutive letters being adjacent to each other.
 +
~afatperson
 +
 +
==Solution 2 (Official MAA)==
 +
Ayako (<math>A</math>), Billy <math>(B)</math>, Carlos <math>(C)</math>, Dahlia <math>(D)</math>, Ehuang <math>(E)</math>, and Frank <math>(F)</math> originally sat in the order <math>ABCDEF</math>.
 +
Let <math>T(XY)</math> denote the set of seatings where <math>X</math> and <math>Y</math> sit next to each other after the break. Then the required number of seating orders is given by the Inclusion-Exclusion Principle as
 +
<cmath>6!-\big(|T(AB)|+|T(BC)|+|T(CD)|+|T(DE)|+|T(EF)|\big)+</cmath><cmath>\big(|T(AB)\cap T(BC)|+|T(AB)\cap T(CD)|+\cdots\big) - \cdots.</cmath>Each term can be calculated separately.
 +
 +
(a) <math>|T(AB)|=|T(BC)|=|T(CD)|=|T(DE)|=|T(EF)|=2\cdot5!=240.</math> Because there are <math>5</math> terms, the sum is <math>5\cdot240=1200</math>.
 +
 +
(b) For <math>|T(XY)\cap T(ZW)|</math>, if <math>Y=Z</math>, then <math>XYW</math> must sit consecutively, so <math>|T(XY)\cap T(ZW)|=2\cdot4!=48</math>. There are <math>4</math> terms that satisfy <math>Y=Z</math>, so the sum is <math>4\cdot 48=192</math>. If <math>XY</math> and <math>ZW</math> are pairwise disjoint, then <math>|T(XY)\cap T(ZW)|=2^2\cdot4!=96</math>. There are <math>6</math> terms, so the sum is <math>6\cdot96=576</math>.
 +
 +
(c) If there are at least three pairs that sit next to each other, consider these three subcases:
 +
If the three pairs are consecutive, the sum is <math>3\cdot2\cdot3!=36</math>.
 +
If exactly two of the pairs are consecutive, the sum is <math>6\cdot2^2\cdot3!=144</math>.
 +
If none of the three pairs is consecutive, the sum is <math>1\cdot2^3\cdot3!=48.</math>
 +
 +
(d) If there are at least four pairs that sit next to each other, then if the pairs are consecutive, the sum is <math>2\cdot2\cdot2!=8</math>. If the pairs are not consecutive, then the sum is <math>3\cdot2^2\cdot2!=24</math>.
 +
 +
(e) If all five pairs sit next to each other, the number is <math>1\cdot2\cdot1!=2</math>.
 +
 +
Therefore the required number of seating orders is<cmath>6!-1200+(192+576)-{(36+144+48)+(8+24)-2}=90.</cmath>
 +
 +
Note: See the [https://oeis.org/A002464 A002464 of the On-Line Encyclopedia of Integer Sequences] for equivalent formulations.
 +
 +
==Solution 3==
 +
 +
We proceed with casework based on the person who sits first after the break.
 +
 +
<math>\textbf{Case 1:}</math> A is first. Then the first three people in the row can be ACE, ACF, ADB, ADF, AEB, AEC, AFB, AFC, or AFD, which yield 2, 1, 2, 2, 1, 2, 0, 1, and 1 possible configurations, respectively, implying 2 + 1 + 2 + 2 + 1 + 2 + 0 + 1 + 1 = 12 possible configurations in this case.
 +
 +
<math>\textbf{Case 2:}</math> B is first. Then the first three people in the row can be BDA, BDF, BEA, BEC, BFA, BFC, or BFD, which yield 2, 4, 2, 4, 0, 1, and 2 possible configurations, respectively, implying 2 + 4 + 2 + 4 + 0 + 1 + 2 = 15 possible configurations in this case.
 +
 +
<math>\textbf{Case 3:}</math> C is first. Then the first three people in the row can be CAD, CAE, CAF, CEA, CEB, CFA, CFB, or CFD, which yield 1, 2, 1, 4, 4, 2, 2, and 2 possible configurations, respectively, implying 1 + 2 + 1 + 4 + 4 + 2 + 2 + 2 = 18 possible configurations in this case.
 +
 +
Finally, the number of valid configurations for A and F, B and E, and C and D are equal by symmetry, so our final answer is 2(12 + 15 + 18), which computes to be <math>\boxed{090}.</math> ~peace09
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=Bh04e_J5YGs
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2020|n=II|num-b=8|num-a=10}}
 
{{AIME box|year=2020|n=II|num-b=8|num-a=10}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 15:21, 18 October 2021

Problem

While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.

Solution (Bash)

There are $2^{5}-1$ intersections that we must consider if we are to perform a PIE bash on this problem. Since we don't really want to think that hard, and bashing does not take that long for this problem, we can write down half of all permutations that satisfy the conditions presented in the problem in "lexicographically next" order to keep track easily. We do this for all cases such that the first "person" is $A-C$, and multiply by two, since the number of working permutations with $D-F$ as the first person is the same as if it were $A-C$, hence, after doing such a bash, we get $45\times2=90$ permutations that result in no consecutive letters being adjacent to each other. ~afatperson

Solution 2 (Official MAA)

Ayako ($A$), Billy $(B)$, Carlos $(C)$, Dahlia $(D)$, Ehuang $(E)$, and Frank $(F)$ originally sat in the order $ABCDEF$. Let $T(XY)$ denote the set of seatings where $X$ and $Y$ sit next to each other after the break. Then the required number of seating orders is given by the Inclusion-Exclusion Principle as \[6!-\big(|T(AB)|+|T(BC)|+|T(CD)|+|T(DE)|+|T(EF)|\big)+\]\[\big(|T(AB)\cap T(BC)|+|T(AB)\cap T(CD)|+\cdots\big) - \cdots.\]Each term can be calculated separately.

(a) $|T(AB)|=|T(BC)|=|T(CD)|=|T(DE)|=|T(EF)|=2\cdot5!=240.$ Because there are $5$ terms, the sum is $5\cdot240=1200$.

(b) For $|T(XY)\cap T(ZW)|$, if $Y=Z$, then $XYW$ must sit consecutively, so $|T(XY)\cap T(ZW)|=2\cdot4!=48$. There are $4$ terms that satisfy $Y=Z$, so the sum is $4\cdot 48=192$. If $XY$ and $ZW$ are pairwise disjoint, then $|T(XY)\cap T(ZW)|=2^2\cdot4!=96$. There are $6$ terms, so the sum is $6\cdot96=576$.

(c) If there are at least three pairs that sit next to each other, consider these three subcases: If the three pairs are consecutive, the sum is $3\cdot2\cdot3!=36$. If exactly two of the pairs are consecutive, the sum is $6\cdot2^2\cdot3!=144$. If none of the three pairs is consecutive, the sum is $1\cdot2^3\cdot3!=48.$

(d) If there are at least four pairs that sit next to each other, then if the pairs are consecutive, the sum is $2\cdot2\cdot2!=8$. If the pairs are not consecutive, then the sum is $3\cdot2^2\cdot2!=24$.

(e) If all five pairs sit next to each other, the number is $1\cdot2\cdot1!=2$.

Therefore the required number of seating orders is\[6!-1200+(192+576)-{(36+144+48)+(8+24)-2}=90.\]

Note: See the A002464 of the On-Line Encyclopedia of Integer Sequences for equivalent formulations.

Solution 3

We proceed with casework based on the person who sits first after the break.

$\textbf{Case 1:}$ A is first. Then the first three people in the row can be ACE, ACF, ADB, ADF, AEB, AEC, AFB, AFC, or AFD, which yield 2, 1, 2, 2, 1, 2, 0, 1, and 1 possible configurations, respectively, implying 2 + 1 + 2 + 2 + 1 + 2 + 0 + 1 + 1 = 12 possible configurations in this case.

$\textbf{Case 2:}$ B is first. Then the first three people in the row can be BDA, BDF, BEA, BEC, BFA, BFC, or BFD, which yield 2, 4, 2, 4, 0, 1, and 2 possible configurations, respectively, implying 2 + 4 + 2 + 4 + 0 + 1 + 2 = 15 possible configurations in this case.

$\textbf{Case 3:}$ C is first. Then the first three people in the row can be CAD, CAE, CAF, CEA, CEB, CFA, CFB, or CFD, which yield 1, 2, 1, 4, 4, 2, 2, and 2 possible configurations, respectively, implying 1 + 2 + 1 + 4 + 4 + 2 + 2 + 2 = 18 possible configurations in this case.

Finally, the number of valid configurations for A and F, B and E, and C and D are equal by symmetry, so our final answer is 2(12 + 15 + 18), which computes to be $\boxed{090}.$ ~peace09

Video Solution

https://www.youtube.com/watch?v=Bh04e_J5YGs

See Also

2020 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 8
Followed by
Problem 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

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