2018 AIME II Problems/Problem 11
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
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.