Difference between revisions of "2018 AIME II Problems/Problem 11"
(→Solution 3 (needs explanation)) |
|||
(17 intermediate revisions by 7 users not shown) | |||
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> 6 ways | 2 4 _ 6 _ _ <math>\implies</math> 6 ways | ||
Line 70: | Line 68: | ||
− | <math>24 + 18 | + | <math>24 + 18 + 4 + 6 + 6 + 6 + 4 + 2 + 1 = 71</math> ways |
Line 91: | Line 89: | ||
If <math>6</math> is the fourth number, then we cannot have the following: | If <math>6</math> is the fourth number, then we cannot have the following: | ||
+ | |||
1 _ _ 6 _ _ <math>\implies</math> 24 ways | 1 _ _ 6 _ _ <math>\implies</math> 24 ways | ||
Line 123: | Line 122: | ||
Grand Total : <math>120 + 96 + 90 + 84 + 71 = \boxed{461}</math> | Grand Total : <math>120 + 96 + 90 + 84 + 71 = \boxed{461}</math> | ||
− | ==Solution 3 ( | + | ==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> | 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> | + | 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>. |
− | |||
− | For every <math>i \in S</math>, we can divide <math>S</math> into two | ||
− | |||
− | 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 | ||
− | |||
− | Notice that according to the condition of this problem, if you sum | ||
− | + | ~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>. | ||
− | <cmath> | + | 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> | ||
+ | ==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> | + | <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> | ||
+ | ~sigma | ||
− | |||
{{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}} |
Revision as of 00:03, 15 May 2022
Contents
Problem
Find the number of permutations of such that for each with , at least one of the first terms of the permutation is greater than .
Solution 1
If the first number is , then there are no restrictions. There are , or ways to place the other numbers.
If the first number is , can go in four places, and there are ways to place the other numbers. ways.
If the first number is , ....
4 6 _ _ _ _ 24 ways
4 _ 6 _ _ _ 24 ways
4 _ _ 6 _ _ 24 ways
4 _ _ _ 6 _ 5 must go between and , so there are ways.
ways if 4 is first.
If the first number is , ....
3 6 _ _ _ _ 24 ways
3 _ 6 _ _ _ 24 ways
3 1 _ 6 _ _ 4 ways
3 2 _ 6 _ _ 4 ways
3 4 _ 6 _ _ 6 ways
3 5 _ 6 _ _ 6 ways
3 5 _ _ 6 _ 6 ways
3 _ 5 _ 6 _ 6 ways
3 _ _ 5 6 _ 4 ways
ways
If the first number is , ....
2 6 _ _ _ _ 24 ways
2 _ 6 _ _ _ 18 ways
2 3 _ 6 _ _ 4 ways
2 4 _ 6 _ _ 6 ways
2 5 _ 6 _ _ 6 ways
2 5 _ _ 6 _ 6 ways
2 _ 5 _ 6 _ 4 ways
2 4 _ 5 6 _ 2 ways
2 3 4 5 6 1 1 way
ways
Grand Total :
Solution 2
If is the first number, then there are no restrictions. There are , or ways to place the other numbers.
If is the second number, then the first number can be or , and there are ways to place the other numbers. ways.
If is the third number, then we cannot have the following:
1 _ 6 _ _ _ 24 ways
2 1 6 _ _ _ 6 ways
ways
If is the fourth number, then we cannot have the following:
1 _ _ 6 _ _ 24 ways
2 1 _ 6 _ _ 6 ways
2 3 1 6 _ _ 2 ways
3 1 2 6 _ _ 2 ways
3 2 1 6 _ _ 2 ways
ways
If is the fifth number, then we cannot have the following:
_ _ _ _ 6 5 24 ways
1 5 _ _ 6 _ 6 ways
1 _ 5 _ 6 _ 6 ways
2 1 5 _ 6 _ 2 ways
1 _ _ 5 6 _ 6 ways
2 1 _ 5 6 _ 2 ways
2 3 1 5 6 4, 3 1 2 5 6 4, 3 2 1 5 6 4 3 ways
ways
Grand Total :
Solution 3 (General Case)
First let us look at the General Case of this kind of Permutation: Consider this kind of Permutation of set for arbitrary
It is easy to count the total number of the permutation () of : For every , we can divide into two subsets: Define permutation as the permutation satisfy the condition of this problem. Then according to the condition of this problem, for each , is not a permutation of set . For each , mark the number of permutation of set as , where , mark the number of permutation for set as ; then, according to the condition of this problem, the permutation for is unrestricted, so the number of the unrestricted permutation of is . As a result, for each , the total number of permutation is Notice that according to the condition of this problem, if you sum all up, you will get the total number of permutation of , that is, Put , we will have So the total number of permutations satisify this problem is .
~Solution by (Frank FYC)
Solution 4 (PIE)
Let be the set of permutations such that there is no number greater than in the first places. Note that for all and that the set of restricted permutations is .
We will compute the cardinality of this set with PIE. To finish,
Solution 5 (Recursion)
Define the function as the amount of permutations with maximum digit and string length that satisfy the condition within bounds. For example, would be the amount of ways to make a string with length with the highest digit being . We wish to obtain .
To generate recursion, consider how we would get to from for all such that . We could either jump from the old maximum to the new by concatenating the old string and the new digit , or one could retain the maximum, in which case . To retain the maximum, one would have to pick a new available digit not exceeding .
In the first case, there is only one way to pick the new digit, namely picking . For the second case, there are digits left to choose, because there are digits between 1 and total and there are digits already chosen below or equal to . Thus, . Now that we have the recursive function, we can start evaluating the values of until we get to .
Our requested answer is thus ~sigma
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.