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
Check the Answer
But try the problem first...
Answer: is 486.
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
Other useful links
- https://www.cheenta.com/inequations-and-conditions-isi-b-stat-tomato-problem/
- https://www.youtube.com/watch?v=ST58GTF95t4&t=140s