Let the number of permutations $a_{1} a_{2} a_{3} a_{4} a_{5} a_{6}$ of the six integers from 1 to 6 such that for all $i$ from 1 to 5, $a_{i + 1}$ does not exceed $a_{i}$ by 1is N. Find greatest integer less than or equal to $\frac{N}{25} .$

see full answer

Your Exam Success, Personally Taken Care Of

1:1 expert mentors customize learning to your strength and weaknesses – so you score higher in school , IIT JEE and NEET entrance exams.

An Intiative by Sri Chaitanya

answer is 12.

(Unlock A.I Detailed Solution for FREE)

Best Courses for You

JEE

NEET

Foundation JEE

Foundation NEET

CBSE

Detailed Solution

Let $S$ be the set of permutations of the six integers from 1 to 6. Then $| S | = 6! = 720.$ Define $P (i)$ to be the subset of $P (i)$ such that the digit $i + 1$ follows immediately Then

$\sum_{i} | P (i) | = \sum_{i_{1} < i_{2}} | P (i_{i}) \cap P (i_{2}) | = (\begin{matrix} 5 \\ 2 \end{matrix}) 4!$
$\sum_{i_{1} < i_{2} < i_{3}} | P (i_{i}) \cap P (i_{2}) \cap P (i_{3}) | = (\begin{matrix} 5 \\ 3 \end{matrix}) 3!$

$\sum_{i_{1} < i_{2} < i_{3} < i_{4}} | P (i_{i}) \cap P (i_{2}) \cap P (i_{3}) \cap P (i_{4}) | = (\begin{matrix} 5 \\ 4 \end{matrix}) 2!$

$| P (1) \cap P (2) \cap P (3) \cap P (4) \cap P (5) | = (\begin{matrix} 5 \\ 5 \end{matrix}) 1!$

By the Principle of Inclusion and Exclusion, the required number is

$6! - (\begin{matrix} 5 \\ 1 \end{matrix}) 5! + (\begin{matrix} 5 \\ 2 \end{matrix}) 4! - (\begin{matrix} 5 \\ 3 \end{matrix}) 3! + (\begin{matrix} 5 \\ 4 \end{matrix}) 2! - (\begin{matrix} 5 \\ 5 \end{matrix}) 1! = 309.$