GATE 2020 CS Q.42: solution and answer

Official answer: 12Source: Official answer key, GATE 2020 CS (IIT Delhi)

1. In LILAC the characters sit at positions $1,2,3,4,5$ as $L,I,L,A,C$. So $L$ is originally at positions $1$ and $3$, $I$ at $2$, $A$ at $4$ and $C$ at $5$. The two $L$'s are identical, so the condition on them is that neither $L$ may sit in position $1$ or $3$.

2. Hence the two $L$'s must occupy two of the positions $\{2,4,5\}$. There are $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ choices. The remaining three positions are filled by $I,A,C$ in some order, and each of these three letters keeps its own restriction.

3. Case $L$ at $\{2,4\}$: the free positions are $1,3,5$. Positions $2$ and $4$ (the original places of $I$ and $A$) are occupied, so $I$ and $A$ are unrestricted. Only $C$ must avoid position $5$. Count: $3!-2!=6-2=4$.

4. Case $L$ at $\{2,5\}$: the free positions are $1,3,4$. Position $2$ is occupied, so $I$ is unrestricted. Position $5$ is occupied, so $C$ is unrestricted. Only $A$ must avoid position $4$. Count: $3!-2!=4$.

5. Case $L$ at $\{4,5\}$: the free positions are $1,2,3$. $A$ and $C$ are unrestricted. Only $I$ must avoid position $2$. Count: $3!-2!=4$.

6. The three cases are disjoint, because they place the $L$'s differently. Total $=4+4+4=12$.