Difference between revisions of "2015 AIME II Problems/Problem 10"
(Create Page) |
(→Solution) |
||
| (15 intermediate revisions by 10 users not shown) | |||
| Line 1: | Line 1: | ||
| − | ==Problem | + | ==Problem== |
Call a permutation <math>a_1, a_2, \ldots, a_n</math> of the integers <math>1, 2, \ldots, n</math> ''quasi-increasing'' if <math>a_k \leq a_{k+1} + 2</math> for each <math>1 \leq k \leq n-1</math>. For example, 53421 and 14253 are quasi-increasing permutations of the integers <math>1, 2, 3, 4, 5</math>, but 45123 is not. Find the number of quasi-increasing permutations of the integers <math>1, 2, \ldots, 7</math>. | Call a permutation <math>a_1, a_2, \ldots, a_n</math> of the integers <math>1, 2, \ldots, n</math> ''quasi-increasing'' if <math>a_k \leq a_{k+1} + 2</math> for each <math>1 \leq k \leq n-1</math>. For example, 53421 and 14253 are quasi-increasing permutations of the integers <math>1, 2, 3, 4, 5</math>, but 45123 is not. Find the number of quasi-increasing permutations of the integers <math>1, 2, \ldots, 7</math>. | ||
| + | |||
| + | ==Solution== | ||
| + | |||
| + | The simple recurrence can be found. | ||
| + | |||
| + | When inserting an integer <math>n</math> into a string with <math>n - 1</math> integers, we notice that the integer <math>n</math> has 3 spots where it can go: before <math>n - 1</math>, before <math>n - 2</math>, and at the very end. | ||
| + | |||
| + | Ex. Inserting 4 into the string 123: | ||
| + | 4 can go before the 2 (1423), before the 3 (1243), and at the very end (1234). | ||
| + | |||
| + | Only the addition of the next number, <math>n</math>, will change anything. | ||
| + | |||
| + | Thus the number of permutations with <math>n</math> elements is three times the number of permutations with <math>n-1</math> elements. | ||
| + | |||
| + | Start with <math>n=3</math> since all <math>6</math> permutations work. And go up: <math>18, 54, 162, 486</math>. | ||
| + | |||
| + | Thus for <math>n=7</math> there are <math>2*3^5=\boxed{486}</math> permutations. | ||
| + | |||
| + | When you are faced with a brain-fazing equation and combinatorics is part of the problem, use recursion! This same idea appeared on another AIME with an 8-box problem. | ||
| + | |||
| + | ==See also== | ||
| + | * [http://www.artofproblemsolving.com/wiki/index.php?title=2006_AIME_I_Problems/Problem_11 2006 AIME I Problem 11] | ||
| + | {{AIME box|year=2015|n=II|num-b=9|num-a=11}} | ||
| + | {{MAA Notice}} | ||
| + | |||
| + | [[Category: Intermediate Combinatorics Problems]] | ||
Latest revision as of 11:15, 25 June 2024
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 
into a string with 
integers, we notice that the integer has 3 spots where it can go: before , before 
, and at the very end.
Ex. Inserting 4 into the string 123: 4 can go before the 2 (1423), before the 3 (1243), and at the very end (1234).
Only the addition of the next number, , will change anything.
Thus the number of permutations with elements is three times the number of permutations with 
elements.
Start with 
since all 
permutations work. And go up: 
.
Thus for 
there are 
permutations.
When you are faced with a brain-fazing equation and combinatorics is part of the problem, use recursion! This same idea appeared on another AIME with an 8-box problem.
See also
| 2015 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 9 |
Followed by Problem 11 | |
| 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. 
