2018 AIME II Problems/Problem 11: Difference between revisions

Revision as of 23:02, 14 May 2022

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}$

Solution 5 (Recursion)

Define the function $f(p,q)$ as the amount of permutations with maximum digit $q$ and string length $p$ that satisfy the condition within bounds. For example, $f(4,5)$ would be the amount of ways to make a string with length $4$ with the highest digit being $5$ . We wish to obtain $f(6,6)=f(5,6)$ .

To generate recursion, consider how we would get to $f(p,q)$ from $f(p-1,a)$ for all $a$ such that $p\le{a}\le6$ . We could either jump from the old maximum $a$ to the new $q$ by concatenating the old string and the new digit $q$ , or one could retain the maximum, in which case $a=q$ . To retain the maximum, one would have to pick a new available digit not exceeding $q$ .

In the first case, there is only one way to pick the new digit, namely picking $q$ . For the second case, there are $q-p+1$ digits left to choose, because there are $q$ digits between 1 and $q$ total and there are $p-1$ digits already chosen below or equal to $q$ . Thus, $f(p,q)=[\sum^{q-1}_{n=p}f(p-1,n)] + (q-p+1)f(p-1,q)$ . Now that we have the recursive function, we can start evaluating the values of $f(p,q)$ until we get to $f(6,6)=f(5,6)$ .

$f(2,3)=3, f(2,4)=5, f(2,5)=7, f(2,6)=9$ $f(3,4)=13, f(3,5)=29, f(3,6)=51$ $f(4,5)=71, f(4,6)=195$ $f(5,6)=461$ Our requested answer is thus $\boxed{461}$

2018 AIME II (Problems • Answer Key • Resources)
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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

@@ Line 144: / Line 144: @@
 </cmath>
 To finish, <math>720 - 372 + 152 - 48 + 10 - 1 = \boxed{461}</math>
+==Solution 5 (Recursion)==
+Define the function <math>f(p,q)</math> as the amount of permutations with maximum digit <math>q</math> and string length <math>p</math> that satisfy the condition within bounds. For example, <math>f(4,5)</math> would be the amount of ways to make a string with length <math>4</math> with the highest digit being <math>5</math>. We wish to obtain <math>f(6,6)=f(5,6)</math>.
+To generate recursion, consider how we would get to <math>f(p,q)</math> from <math>f(p-1,a)</math> for all <math>a</math> such that <math>p\le{a}\le6</math>. We could either jump from the old maximum <math>a</math> to the new <math>q</math> by concatenating the old string and the new digit <math>q</math>, or one could retain the maximum, in which case <math>a=q</math>. To retain the maximum, one would have to pick a new available digit not exceeding <math>q</math>.
+In the first case, there is only one way to pick the new digit, namely picking <math>q</math>. For the second case, there are <math>q-p+1</math> digits left to choose, because there are <math>q</math> digits between 1 and <math>q</math> total and there are <math>p-1</math> digits already chosen below or equal to <math>q</math>. Thus, <math>f(p,q)=[\sum^{q-1}_{n=p}f(p-1,n)] + (q-p+1)f(p-1,q)</math>. Now that we have the recursive function, we can start evaluating the values of <math>f(p,q)</math> until we get to <math>f(6,6)=f(5,6)</math>.
+<cmath>f(2,3)=3, f(2,4)=5, f(2,5)=7, f(2,6)=9</cmath>
+<cmath>f(3,4)=13, f(3,5)=29, f(3,6)=51</cmath>
+<cmath>f(4,5)=71, f(4,6)=195</cmath>
+<cmath>f(5,6)=461</cmath>
+Our requested answer is thus <math>\boxed{461}</math>
 {{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 {{MAA Notice}}

Page

Toolbox

Search