Difference between revisions of "2018 AIME II Problems/Problem 11"
(→Solution 4 (You won't get 458, 459, 460, 462, 465, 467, etc. with this method!!!)) |
(→Solution 4 (You won't get 458, 459, 460, 462, 465, 467, etc. with this method!!!)) |
||
Line 130: | Line 130: | ||
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> 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> | + | 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>. |
− | |||
− | 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 by <math>BladeRunnerAUG</math> (Frank FYC) |
Revision as of 22:32, 6 October 2018
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 _ _ 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 (needs explanation)
The answer is .
Solution 4 (You won't get 458, 459, 460, 462, 465, 467, etc. with this method!!!)
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)
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.