Difference between revisions of "2018 AIME II Problems/Problem 11"

m (Solution)
m (Solution 4 (PIE))
 
(21 intermediate revisions by 6 users not shown)
Line 3: Line 3:
 
Find the number of permutations of <math>1, 2, 3, 4, 5, 6</math> such that for each <math>k</math> with <math>1</math> <math>\leq</math> <math>k</math> <math>\leq</math> <math>5</math>, at least one of the first <math>k</math> terms of the permutation is greater than <math>k</math>.
 
Find the number of permutations of <math>1, 2, 3, 4, 5, 6</math> such that for each <math>k</math> with <math>1</math> <math>\leq</math> <math>k</math> <math>\leq</math> <math>5</math>, at least one of the first <math>k</math> terms of the permutation is greater than <math>k</math>.
  
==Solution==
+
==Solution 1==
  
 
If the first number is <math>6</math>, then there are no restrictions. There are <math>5!</math>, or <math>120</math> ways to place the other <math>5</math> numbers.
 
If the first number is <math>6</math>, then there are no restrictions. There are <math>5!</math>, or <math>120</math> ways to place the other <math>5</math> numbers.
Line 54: Line 54:
  
 
2 3 _ 6 _ _ <math>\implies</math> 4 ways
 
2 3 _ 6 _ _ <math>\implies</math> 4 ways
 
2 4 _ 6 _ _ <math>\implies</math> 4 ways
 
  
 
2 4 _ 6 _ _ <math>\implies</math> 6 ways
 
2 4 _ 6 _ _ <math>\implies</math> 6 ways
Line 70: Line 68:
  
  
<math>24 + 18 + 4 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71</math> ways
+
<math>24 + 18 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71</math> ways
 +
 
 +
 
 +
Grand Total : <math>120 + 96 + 90 + 84 + 71 = \boxed{461}</math>
 +
 
 +
==Solution 2==
 +
If <math>6</math> is the first number, then there are no restrictions. There are <math>5!</math>, or <math>120</math> ways to place the other <math>5</math> numbers.
 +
 
 +
 
 +
If <math>6</math> is the second number, then the first number can be <math>2, 3, 4,</math> or <math>5</math>, and there are <math>4!</math> ways to place the other <math>4</math> numbers. <math>4 \cdot 4! = 96</math> ways.
 +
 
 +
 
 +
If <math>6</math> is the third number, then we cannot have the following:
 +
 
 +
1 _ 6 _ _ _ <math>\implies</math> 24 ways
 +
 
 +
2 1 6 _ _ _ <math>\implies</math> 6 ways
 +
 
 +
<math>120 - 24 - 6 = 90</math> ways
 +
 
 +
If <math>6</math> is the fourth number, then we cannot have the following:
 +
 
 +
1 _ _ 6 _ _ <math>\implies</math> 24 ways
 +
 
 +
2 1 _ 6 _ _ <math>\implies</math> 6 ways
 +
 
 +
2 3 1 6 _ _ <math>\implies</math> 2 ways
 +
 
 +
3 1 2 6 _ _ <math>\implies</math> 2 ways
 +
 
 +
3 2 1 6 _ _ <math>\implies</math> 2 ways
 +
 
 +
<math>120 - 24 - 6 - 2 - 2 - 2 = 84</math> ways
 +
 
 +
If <math>6</math> is the fifth number, then we cannot have the following:
 +
 
 +
_ _ _ _ 6 5 <math>\implies</math> 24 ways
 +
 
 +
1 5 _ _ 6 _ <math>\implies</math> 6 ways
 +
 
 +
1 _ 5 _ 6 _ <math>\implies</math> 6 ways
 +
 
 +
2 1 5 _ 6 _ <math>\implies</math> 2 ways
 +
 
 +
1 _ _ 5 6 _ <math>\implies</math> 6 ways
 +
 
 +
2 1 _ 5 6 _ <math>\implies</math> 2 ways
 +
 
 +
2 3 1 5 6 4, 3 1 2 5 6 4, 3 2 1 5 6 4 <math>\implies</math> 3 ways
 +
 
 +
<math>120 - 24 - 6 - 6 - 2 - 6 - 2 - 3 = 71</math> ways
 +
 
 +
Grand Total : <math>120 + 96 + 90 + 84 + 71 = \boxed{461}</math>
 +
 
 +
==Solution 3 (General Case)==
 +
 
 +
First let us look at the General Case of this kind of Permutation: Consider this kind of Permutation of set <cmath>S=\{1,2,...,n\}</cmath> for arbitrary <math>n \in N</math>
 +
 
 +
It is easy to count the total number of the permutation (<math>N</math>) of <math>S</math>: <cmath>N=n!</cmath> For every <math>i \in S</math>, we can divide <math>S</math> into two subsets: <cmath>S_{1\to i}=\{1,2,...i\}; S_{i+1\to n}=\{i+1,i+2,...,n\}</cmath> Define permutation <math>P</math> as the permutation satisfy the condition of this problem. Then according to the condition of this problem, for each <math>i\in \{1,2,...,n-1\}</math>, <math>P</math> is not a permutation of set <math>S_{1\to i}</math>. For each <math>i\in \{1,2,...,n\}</math>, mark the number of permutation <math>P</math> of set <math>S</math> as <math>P_{k}</math>, where <math>k=i</math>, mark the number of permutation <math>P</math> for set <math>S_{i+1\to n}</math> as <math>P_{i}</math>; then, according to the condition of this problem, the permutation for <math>S_{i+1\to n}</math> is unrestricted, so the number of the unrestricted permutation of <math>S_{i+1\to n}</math> is <math>(n-i)!</math>. As a result, for each <math>i\in \{1,2,...,n\}</math>, the total number of permutation <math>P</math> is <cmath>P_{k}=P_{i}(n-i)!</cmath> Notice that according to the condition of this problem, if you sum all <math>P_{k}</math> up, you will get the total number of permutation of <math>S</math>, that is, <cmath>N=\sum^{n}_{k=1}{P_{k}}=\sum^{n}_{i=1}{P_{i}(n-i)!}=n!</cmath> Put <math>n=1,2,3,...,6</math>, we will have <cmath>P_{1}=1</cmath> <cmath>P_{2}=1</cmath> <cmath>P_{3}=3</cmath> <cmath>P_{4}=13</cmath> <cmath>P_{5}=71</cmath> <cmath>P_{6}=461</cmath> So the total number of permutations satisify this problem is <math>P_{6}=\boxed{461}</math>.
 +
 
 +
~Solution by <math>BladeRunnerAUG</math> (Frank FYC)
  
 +
==Solution 4 (PIE)==
 +
Let <math>A_i</math> be the set of permutations such that there is no number greater than <math>i</math> in the first <math>i</math> places. Note that <math>\bigcap^{k}_{i=0}{A_{b_i}}=\prod^k_{i=1}{(b_i-b_{i-1})!}</math> for all <math>1\le b_0 < b_1\cdots < b_k \le 5</math> and that the set of restricted permutations is <math>A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5</math>.
  
Grand Total : <math>120 + 96 + 90 + 84 + 71 = </math><math>\boxed{461}</math>
+
We will compute the cardinality of this set with PIE.
 +
<cmath>
 +
\begin{align*}
 +
&|A_1| + |A_2| + |A_3| + |A_4| + |A_5|\\ = &120 + 48 + 36 + 48 + 120 = 372\\ \\
 +
&|A_1 \cap A_2| + |A_1 \cap A_3| + |A_1 \cap A_4| + |A_1 \cap A_5| + |A_2 \cap A_3|\\ + &|A_2 \cap A_4| + |A_2 \cap A_5| + |A_3 \cap A_4| + |A_3 \cap A_5| + |A_4 \cap A_5|\\=&24+12+12+24+12+8+12+12+12+24=152\\ \\
 +
&|A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_2 \cap A_5| + |A_1 \cap A_3 \cap A_4| + |A_1 \cap A_3 \cap A_5|\\ +& |A_1 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_5| +  |A_2 \cap A_4 \cap A_5| + |A_3 \cap A_4 \cap A_5|\\=&6 + 4 + 6 + 4 + 4 + 6 + 4 + 4 + 4 + 6 = 48\\ \\
 +
&|A_1 \cap A_2 \cap A_3 \cap A_4| + |A_1 \cap A_2 \cap A_3 \cap A_5| + |A_1 \cap A_2 \cap A_4 \cap A_5| + |A_1 \cap A_3 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4 \cap A_5|\\=&2 + 2 + 2 + 2 + 2 = 10\\ \\
 +
&|A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5| = 1
 +
\end{align*}
 +
</cmath>
 +
To finish, <math>720 - 372 + 152 - 48 + 10 - 1 = \boxed{461}</math>
  
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 19:22, 24 February 2021

Problem

Find the number of permutations of $1, 2, 3, 4, 5, 6$ such that for each $k$ with $1$ $\leq$ $k$ $\leq$ $5$, at least one of the first $k$ terms of the permutation is greater than $k$.

Solution 1

If the first number is $6$, then there are no restrictions. There are $5!$, or $120$ ways to place the other $5$ numbers.


If the first number is $5$, $6$ can go in four places, and there are $4!$ ways to place the other $4$ numbers. $4 \cdot 4! = 96$ ways.


If the first number is $4$, ....

4 6 _ _ _ _ $\implies$ 24 ways

4 _ 6 _ _ _ $\implies$ 24 ways

4 _ _ 6 _ _ $\implies$ 24 ways

4 _ _ _ 6 _ $\implies$ 5 must go between $4$ and $6$, so there are $3 \cdot 3! = 18$ ways.

$24 + 24 + 24 + 18 = 90$ ways if 4 is first.


If the first number is $3$, ....

3 6 _ _ _ _ $\implies$ 24 ways

3 _ 6 _ _ _ $\implies$ 24 ways

3 1 _ 6 _ _ $\implies$ 4 ways

3 2 _ 6 _ _ $\implies$ 4 ways

3 4 _ 6 _ _ $\implies$ 6 ways

3 5 _ 6 _ _ $\implies$ 6 ways

3 5 _ _ 6 _ $\implies$ 6 ways

3 _ 5 _ 6 _ $\implies$ 6 ways

3 _ _ 5 6 _ $\implies$ 4 ways

$24 + 24 + 4 + 4 + 6 + 6 + 6 + 6 + 4 = 84$ ways


If the first number is $2$, ....

2 6 _ _ _ _ $\implies$ 24 ways

2 _ 6 _ _ _ $\implies$ 18 ways

2 3 _ 6 _ _ $\implies$ 4 ways

2 4 _ 6 _ _ $\implies$ 6 ways

2 5 _ 6 _ _ $\implies$ 6 ways

2 5 _ _ 6 _ $\implies$ 6 ways

2 _ 5 _ 6 _ $\implies$ 4 ways

2 4 _ 5 6 _ $\implies$ 2 ways

2 3 4 5 6 1 $\implies$ 1 way


$24 + 18 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71$ ways


Grand Total : $120 + 96 + 90 + 84 + 71 = \boxed{461}$

Solution 2

If $6$ is the first number, then there are no restrictions. There are $5!$, or $120$ ways to place the other $5$ numbers.


If $6$ is the second number, then the first number can be $2, 3, 4,$ or $5$, and there are $4!$ ways to place the other $4$ numbers. $4 \cdot 4! = 96$ ways.


If $6$ is the third number, then we cannot have the following:

1 _ 6 _ _ _ $\implies$ 24 ways

2 1 6 _ _ _ $\implies$ 6 ways

$120 - 24 - 6 = 90$ ways

If $6$ is the fourth number, then we cannot have the following:

1 _ _ 6 _ _ $\implies$ 24 ways

2 1 _ 6 _ _ $\implies$ 6 ways

2 3 1 6 _ _ $\implies$ 2 ways

3 1 2 6 _ _ $\implies$ 2 ways

3 2 1 6 _ _ $\implies$ 2 ways

$120 - 24 - 6 - 2 - 2 - 2 = 84$ ways

If $6$ is the fifth number, then we cannot have the following:

_ _ _ _ 6 5 $\implies$ 24 ways

1 5 _ _ 6 _ $\implies$ 6 ways

1 _ 5 _ 6 _ $\implies$ 6 ways

2 1 5 _ 6 _ $\implies$ 2 ways

1 _ _ 5 6 _ $\implies$ 6 ways

2 1 _ 5 6 _ $\implies$ 2 ways

2 3 1 5 6 4, 3 1 2 5 6 4, 3 2 1 5 6 4 $\implies$ 3 ways

$120 - 24 - 6 - 6 - 2 - 6 - 2 - 3 = 71$ ways

Grand Total : $120 + 96 + 90 + 84 + 71 = \boxed{461}$

Solution 3 (General Case)

First let us look at the General Case of this kind of Permutation: Consider this kind of Permutation of set \[S=\{1,2,...,n\}\] for arbitrary $n \in N$

It is easy to count the total number of the permutation ($N$) of $S$: \[N=n!\] For every $i \in S$, we can divide $S$ into two subsets: \[S_{1\to i}=\{1,2,...i\}; S_{i+1\to n}=\{i+1,i+2,...,n\}\] Define permutation $P$ as the permutation satisfy the condition of this problem. Then according to the condition of this problem, for each $i\in \{1,2,...,n-1\}$, $P$ is not a permutation of set $S_{1\to i}$. For each $i\in \{1,2,...,n\}$, mark the number of permutation $P$ of set $S$ as $P_{k}$, where $k=i$, mark the number of permutation $P$ for set $S_{i+1\to n}$ as $P_{i}$; then, according to the condition of this problem, the permutation for $S_{i+1\to n}$ is unrestricted, so the number of the unrestricted permutation of $S_{i+1\to n}$ is $(n-i)!$. As a result, for each $i\in \{1,2,...,n\}$, the total number of permutation $P$ is \[P_{k}=P_{i}(n-i)!\] Notice that according to the condition of this problem, if you sum all $P_{k}$ up, you will get the total number of permutation of $S$, that is, \[N=\sum^{n}_{k=1}{P_{k}}=\sum^{n}_{i=1}{P_{i}(n-i)!}=n!\] Put $n=1,2,3,...,6$, we will have \[P_{1}=1\] \[P_{2}=1\] \[P_{3}=3\] \[P_{4}=13\] \[P_{5}=71\] \[P_{6}=461\] So the total number of permutations satisify this problem is $P_{6}=\boxed{461}$.

~Solution by $BladeRunnerAUG$ (Frank FYC)

Solution 4 (PIE)

Let $A_i$ be the set of permutations such that there is no number greater than $i$ in the first $i$ places. Note that $\bigcap^{k}_{i=0}{A_{b_i}}=\prod^k_{i=1}{(b_i-b_{i-1})!}$ for all $1\le b_0 < b_1\cdots < b_k \le 5$ and that the set of restricted permutations is $A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5$.

We will compute the cardinality of this set with PIE. \begin{align*} &|A_1| + |A_2| + |A_3| + |A_4| + |A_5|\\ = &120 + 48 + 36 + 48 + 120 = 372\\ \\ &|A_1 \cap A_2| + |A_1 \cap A_3| + |A_1 \cap A_4| + |A_1 \cap A_5| + |A_2 \cap A_3|\\ + &|A_2 \cap A_4| + |A_2 \cap A_5| + |A_3 \cap A_4| + |A_3 \cap A_5| + |A_4 \cap A_5|\\=&24+12+12+24+12+8+12+12+12+24=152\\ \\ &|A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_2 \cap A_5| + |A_1 \cap A_3 \cap A_4| + |A_1 \cap A_3 \cap A_5|\\ +& |A_1 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_5| +  |A_2 \cap A_4 \cap A_5| + |A_3 \cap A_4 \cap A_5|\\=&6 + 4 + 6 + 4 + 4 + 6 + 4 + 4 + 4 + 6 = 48\\ \\ &|A_1 \cap A_2 \cap A_3 \cap A_4| + |A_1 \cap A_2 \cap A_3 \cap A_5| + |A_1 \cap A_2 \cap A_4 \cap A_5| + |A_1 \cap A_3 \cap A_4 \cap A_5| + |A_2 \cap A_3 \cap A_4 \cap A_5|\\=&2 + 2 + 2 + 2 + 2 = 10\\ \\ &|A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5| = 1 \end{align*} To finish, $720 - 372 + 152 - 48 + 10 - 1 = \boxed{461}$

2018 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 10
Followed by
Problem 12
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

Invalid username
Login to AoPS