Difference between revisions of "2020 AIME II Problems/Problem 9"
m |
Xhypotenuse (talk | contribs) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 39: | Line 39: | ||
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 | 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 | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | We determine the order of A, B, C, relative to each other. Then, we will insert D, E, F into the alignment and calculate the total number of possibilities. This solution can be visualised as standing in lines rather than sitting on chairs. | ||
+ | |||
+ | There are 6 possible alignments for A, B, and C, but we only evaluate 3 because the other 3 cases can be mirrored to overlap these 3 cases. | ||
+ | |||
+ | <math>\textbf{Case 1: A B C}</math> In this case, there must be a person standing between A and B and also between B and C. Also, D cannot be adjacent to C. There are 9 possibilities. | ||
+ | |||
+ | <math>\textbf{Case 2: A C B}</math> In this case, there must be a person standing between B and C. Also, D cannot be adjacent to C. There are 12 possibilities. | ||
+ | |||
+ | <math>\textbf{Case 3: C A B}</math> In this case, there must be a person standing between A and B. Also, D cannot be adjacent to C. There are 24 possibilities. | ||
+ | |||
+ | So the total number of cases is 2(9+12+24)=<math>\boxed{090}</math>. | ||
+ | |||
+ | -Superdolphin | ||
+ | |||
+ | ==Solution 5 (Recursion, taking less time) == | ||
+ | |||
+ | Consider arrangements of numbers <math>1, 2, 3, ..., n</math>. | ||
+ | |||
+ | Let <math>f(n,k)</math> be the number of arrangements in which <math>1</math> and <math>2</math>, <math>2</math> and <math>3</math>, <math>3</math> and <math>4</math>, ..., <math>k-1</math> and <math>k</math> aren't together. We need to find <math>f(6,6)</math>. | ||
+ | |||
+ | Let <math>d(n,k)</math> be the number of arrangements in which <math>1</math> and <math>2</math>, <math>2</math> and <math>3</math>, <math>3</math> and <math>4</math>, ..., <math>k-2</math> and <math>k-1</math> aren't together, but <math>(k-1)</math> and <math>k</math> are together. | ||
+ | |||
+ | Then, | ||
+ | |||
+ | <cmath>f(n,k+1) = f(n,k) - d(n,k+1) ......(1)</cmath> | ||
+ | |||
+ | <cmath>d(n,k+1) = 2f(n-1,k) + d(n-1,k) ......(2)</cmath> | ||
+ | |||
+ | Hence, | ||
+ | <cmath>f(n,k+1)=f(n,k)-f(n-1,k)-f(n-1,k-1)</cmath> | ||
+ | |||
+ | And because <math>f(n,0) = f(n,1) = n!</math>, it's easy to get <math>f(6,6) = \boxed{090}</math> | ||
+ | |||
+ | |||
+ | <cmath>\begin{tabular}{|c|c|c|c|c|c|c|}\hline | ||
+ | k,n & n=1 & n=2 & n=3 & n=4 & n=5 & n=6\\\hline | ||
+ | k=1 & 1 & 2 & 6 & 24 & 120 & 720\\\hline | ||
+ | k=2 & & 0 & 2 & 12 & 72 & 480\\\hline | ||
+ | k=3 & & & 0 & 4 & 36 & 288\\\hline | ||
+ | k=4 & & & & 2 & 20 & 180\\\hline | ||
+ | k=5 & & & & & 14 & 124\\\hline | ||
+ | k=6 & & & & & & 90\\\hline | ||
+ | \end{tabular}</cmath> | ||
+ | |||
+ | |||
+ | Note: How to get the two equations (1) and (2). | ||
+ | |||
+ | |||
+ | 1. If <math>1</math> and <math>2</math>, <math>2</math> and <math>3</math>, ... , <math>k-1</math> and <math>k</math> aren't together, there are two cases: | ||
+ | |||
+ | (a) <math>k</math> and <math>k+1</math> aren't together. There are <math>f(n,k+1)</math> ways of arrangements. | ||
+ | |||
+ | (b) <math>k</math> and <math>k+1</math> are together. There are <math>d(n,k+1)</math> ways of arrangements. | ||
+ | |||
+ | Thus, <math>f(n,k)=f(n,k+1)+d(n,k+1)</math>, i.e. <math>f(n,k+1)=f(n,k)-d(n,k+1)</math>, which is the first equation. | ||
+ | |||
+ | |||
+ | 2. If <math>1</math> and <math>2</math>, <math>2</math> and <math>3</math>, ... , <math>k-1</math> and <math>k</math> aren't together, but <math>k</math> and <math>k+1</math> are together, there are 2 cases : | ||
+ | |||
+ | (a) <math>k-1</math> isn't together with <math>k</math> or <math>k+1</math>. We first determine the order of <math>k</math> and <math>k+1</math>, then, we can treat them as one number since they should be always together. Hence, the number of arrangements is <math>2f(n-1,k)</math>. | ||
+ | |||
+ | (b) <math>k-1</math> is together with <math>k</math> or <math>k+1</math>. We first determine the order of <math>k</math> and <math>k+1</math>, then treat them as one "super number". Since <math>k-1</math> is together with the "super number", there are <math>2d(n-1,k)</math> ways of arrangements. However, <math>k-1</math> can only be on one side of the "super number" because <math>k-1</math> and <math>k</math> aren't together, so we need to multiple a <math>1/2</math> to the number of arrangements. Finally, there are <math>2d(n-1,k)*(1/2)=d(n-1,k)</math> ways of arrangements. | ||
+ | |||
+ | Thus, <math>d(n,k+1)=2f(n-1,k)+d(n-1,k)</math>, which is the second equation. | ||
+ | |||
+ | |||
+ | ~Shawn | ||
+ | |||
+ | |||
+ | ==Solution 6 (fast) == | ||
+ | |||
+ | We will split up our cases based on the positions of <math>A</math>, <math>B</math>, and <math>C</math> relative to each other. | ||
+ | |||
+ | Case <math>1</math>: <math>A</math> <math>B</math> <math>C</math>: <math>9</math> cases | ||
+ | |||
+ | Case <math>2</math>: <math>A</math> <math>C</math> <math>B</math>: <math>16</math> cases | ||
+ | |||
+ | Case <math>3</math>: <math>B</math> <math>A</math> <math>C</math>: <math>20</math> cases | ||
+ | |||
+ | |||
+ | Since we can reverse the first case to make <math>C</math> <math>B</math> <math>A</math>, reverse the second case to make <math>B</math> <math>C</math> <math>A</math>, and reverse the third case to make <math>C</math> <math>A</math> <math>B</math>, by symmetry we have <math>2(9+16+20) = \boxed{090}</math> ways in total. | ||
+ | |||
+ | |||
+ | ~xHypotenuse | ||
==Video Solution== | ==Video Solution== | ||
Line 49: | Line 136: | ||
{{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}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 00:21, 8 August 2024
Contents
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 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
, and multiply by two, since the number of working permutations with
as the first person is the same as if it were
, hence, after doing such a bash, we get
permutations that result in no consecutive letters being adjacent to each other.
~afatperson
Solution 2 (Official MAA)
Ayako (), Billy
, Carlos
, Dahlia
, Ehuang
, and Frank
originally sat in the order
.
Let
denote the set of seatings where
and
sit next to each other after the break. Then the required number of seating orders is given by the Inclusion-Exclusion Principle as
Each term can be calculated separately.
(a) Because there are
terms, the sum is
.
(b) For , if
, then
must sit consecutively, so
. There are
terms that satisfy
, so the sum is
. If
and
are pairwise disjoint, then
. There are
terms, so the sum is
.
(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 .
If exactly two of the pairs are consecutive, the sum is
.
If none of the three pairs is consecutive, the sum is
(d) If there are at least four pairs that sit next to each other, then if the pairs are consecutive, the sum is . If the pairs are not consecutive, then the sum is
.
(e) If all five pairs sit next to each other, the number is .
Therefore the required number of seating orders is
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.
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.
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.
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 ~peace09
Solution 4
We determine the order of A, B, C, relative to each other. Then, we will insert D, E, F into the alignment and calculate the total number of possibilities. This solution can be visualised as standing in lines rather than sitting on chairs.
There are 6 possible alignments for A, B, and C, but we only evaluate 3 because the other 3 cases can be mirrored to overlap these 3 cases.
In this case, there must be a person standing between A and B and also between B and C. Also, D cannot be adjacent to C. There are 9 possibilities.
In this case, there must be a person standing between B and C. Also, D cannot be adjacent to C. There are 12 possibilities.
In this case, there must be a person standing between A and B. Also, D cannot be adjacent to C. There are 24 possibilities.
So the total number of cases is 2(9+12+24)=.
-Superdolphin
Solution 5 (Recursion, taking less time)
Consider arrangements of numbers .
Let be the number of arrangements in which
and
,
and
,
and
, ...,
and
aren't together. We need to find
.
Let be the number of arrangements in which
and
,
and
,
and
, ...,
and
aren't together, but
and
are together.
Then,
Hence,
And because , it's easy to get
Note: How to get the two equations (1) and (2).
1. If and
,
and
, ... ,
and
aren't together, there are two cases:
(a) and
aren't together. There are
ways of arrangements.
(b) and
are together. There are
ways of arrangements.
Thus, , i.e.
, which is the first equation.
2. If and
,
and
, ... ,
and
aren't together, but
and
are together, there are 2 cases :
(a) isn't together with
or
. We first determine the order of
and
, then, we can treat them as one number since they should be always together. Hence, the number of arrangements is
.
(b) is together with
or
. We first determine the order of
and
, then treat them as one "super number". Since
is together with the "super number", there are
ways of arrangements. However,
can only be on one side of the "super number" because
and
aren't together, so we need to multiple a
to the number of arrangements. Finally, there are
ways of arrangements.
Thus, , which is the second equation.
~Shawn
Solution 6 (fast)
We will split up our cases based on the positions of ,
, and
relative to each other.
Case :
:
cases
Case :
:
cases
Case :
:
cases
Since we can reverse the first case to make
, reverse the second case to make
, and reverse the third case to make
, by symmetry we have
ways in total.
~xHypotenuse
Video Solution
https://www.youtube.com/watch?v=Bh04e_J5YGs
~MathProblemSolvingSkills.com
See Also
2020 AIME II (Problems • Answer Key • Resources) | ||
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.