Difference between revisions of "2015 AIME II Problems/Problem 10"
m (Add Solution Section) |
(→Solution) |
||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| + | |||
| + | The simple recurrence can be found. | ||
| + | |||
| + | When inserting an integer n into a string with n-1 integers, we notice that the integer n has 3 spots where it can go: before n-1, before n-2, and at the very end. | ||
| + | |||
| + | EXAMPLE: | ||
| + | putting 4 into the string 123: | ||
| + | 4 can go before the 2 : 1423, | ||
| + | before the 3: 1243, | ||
| + | and at the very end: 1234. | ||
| + | |||
| + | Thus the number of permutations with n elements is three times the number of permutations with n-1 elements. | ||
| + | |||
| + | For n=3, there are 6 permutations. Thus for n=7 there are 6*3^4 = 486 permutations. | ||
Revision as of 20:55, 26 March 2015
Problem
Call a permutation 
of the integers 
quasi-increasing if 
for each 
. For example, 53421 and 14253 are quasi-increasing permutations of the integers 
, but 45123 is not. Find the number of quasi-increasing permutations of the integers 
.
Solution
The simple recurrence can be found.
When inserting an integer n into a string with n-1 integers, we notice that the integer n has 3 spots where it can go: before n-1, before n-2, and at the very end.
EXAMPLE: putting 4 into the string 123: 4 can go before the 2 : 1423, before the 3: 1243, and at the very end: 1234.
Thus the number of permutations with n elements is three times the number of permutations with n-1 elements.
For n=3, there are 6 permutations. Thus for n=7 there are 6*3^4 = 486 permutations.
