How Cheenta works to ensure student success?
Explore the Back-Story

Sequence and permutations | AIME II, 2015 | Question 10

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME II, 2015 based on Sequence and permutations.

Sequence and permutations - AIME II, 2015

Call a permutation $a_1,a_2,....,a_n$ of the integers 1,2,...,n quasi increasing if $a_k \leq a_{k+1} +2$ for each $1 \leq k \leq n-1$, find the number of quasi increasing permutations of the integers 1,2,....,7.

• is 107
• is 486
• is 840
• cannot be determined from the given information

Key Concepts

Sequence

Permutations

Integers

AIME II, 2015, Question 10

Elementary Number Theory by David Burton

Try with Hints

First hint

While inserting n into a string with n-1 integers, integer n has 3 spots where it can be placed before n-1, before n-2, and at the end

Second Hint

Number of permutations with n elements is three times the number of permutations with n-1 elements

or, number of permutations for n elements=3 $\times$ number of permutations of (n-1) elements

or, number of permutations for n elements=$3^{2}$ number of permutations of (n-2) elements

......

or, number of permutations for n elements=$3^{n-2}$ number of permutations of {n-(n-2)} elements

or, number of permutations for n elements=2 $\times$ $3^{n-2}$

forming recurrence relation as the number of permutations =2 $\times$ $3^{n-2}$

for n=3 all six permutations taken and go up 18, 54, 162, 486

Final Step

for n=7, here $2 \times 3^{5} =486.$

as

sds

Try this beautiful problem from the American Invitational Mathematics Examination I, AIME II, 2015 based on Sequence and permutations.

Sequence and permutations - AIME II, 2015

Call a permutation $a_1,a_2,....,a_n$ of the integers 1,2,...,n quasi increasing if $a_k \leq a_{k+1} +2$ for each $1 \leq k \leq n-1$, find the number of quasi increasing permutations of the integers 1,2,....,7.

• is 107
• is 486
• is 840
• cannot be determined from the given information

Key Concepts

Sequence

Permutations

Integers

AIME II, 2015, Question 10

Elementary Number Theory by David Burton

Try with Hints

First hint

While inserting n into a string with n-1 integers, integer n has 3 spots where it can be placed before n-1, before n-2, and at the end

Second Hint

Number of permutations with n elements is three times the number of permutations with n-1 elements

or, number of permutations for n elements=3 $\times$ number of permutations of (n-1) elements

or, number of permutations for n elements=$3^{2}$ number of permutations of (n-2) elements

......

or, number of permutations for n elements=$3^{n-2}$ number of permutations of {n-(n-2)} elements

or, number of permutations for n elements=2 $\times$ $3^{n-2}$

forming recurrence relation as the number of permutations =2 $\times$ $3^{n-2}$

for n=3 all six permutations taken and go up 18, 54, 162, 486

Final Step

for n=7, here $2 \times 3^{5} =486.$

as

sds

This site uses Akismet to reduce spam. Learn how your comment data is processed.