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

Check the Answer


But try the problem first…

Answer: is 486.

Source
Suggested Reading

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.\)

Header text

as

Header text

sds

Subscribe to Cheenta at Youtube