Difference between revisions of "2015 AIME II Problems/Problem 10"
m (Add Solution Section) |
(→Solution) |
||
(14 intermediate revisions by 9 users not shown) | |||
Line 4: | Line 4: | ||
==Solution== | ==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 12: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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.