AIME 2015 Problem 10

Probability Level 4

Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1 \leq k \leq n-1$ . For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5$ , but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, \ldots, 7$ .

Try more problems of AIME from this set AIME 2015

The answer is 486.

1 solution

Brandon Monsen
Dec 5, 2015

We can find a recursive formula for the number of quasi-increasing sequences of the first $n$ natural numbers.

Let the number of quasi-increasing sequences for the first $n$ natural numbers be $s_{n}$ .

$s_{1}=1$ and for $n=2$ , the $2$ can go anywhere, so $s_{2}=2!$ . For $n=3$ , you can put the $3$ anywhere on any sequence for $n=2$ , so $s_{3}=3!$ .

Now, for $n=4$ , you can't put the $4$ before the $1$ , so there are $4-1$ more options for where to put the $4$ . This means $s_{4}=3! \times 3$ .

For $n=5$ , you can't put the $5$ before the $2$ or $1$ , so there are $5-2$ places to put the $5$ , thus $s_{5}=3! \times 3^{2}$ .

This pattern will hold for $s_{6}$ and $s_{7}$ , so we know that $s_{7}=3! \times 3^{4}=\boxed{486}$

same method, glad I didn't bash it

keanu ac - 4 years ago

AIME 2015 Problem 10

Try more problems of AIME from this set AIME 2015

The answer is 486.

1 solution

0 pending reports