Select the Knights and Save the Princess!

We solve the more general problem when there are $n$ knights and a group of $k$ compatible knights has to be selected for the task. Recall first that by a well-known formula in elementary combinatorics, the number of ways of selecting $k$ objects from a row of $n$ distinct objects so that no two of the selected objects could be adjacent, is given by the binomial coeffcient:

${ n - k + 1 \choose k}$

Consider one particular knight, say, Sir Calvin. Then the group to be selected either includes him or excludes him.

If Calvin is chosen, then his two neighbours cannot be chosen and hence, we must choose $k-1$ more knights from the remaining $n-3$ knights in such a way that no two adjacent knights are selected. By the formula quoted above, this can be done in: ${n-3-(k-1)+1 \choose k-1}$ ways.

If Calvin is not chosen, then we must select all $k$ knights from the $n-1$ remaining knights subject to the same constraint. This can be done in ${n-1-k+1 \choose k}$ ways.

Therefore the total number of number teams is

$f(n,k) = {n-3-(k-1)+1 \choose k-1} + {n-1-k+1 \choose k}$

$= {n-k-1 \choose k-1} + {n-k \choose k}$

$= {n-k-1 \choose k-1} + \dfrac{n-k}{k} {n-k-1 \choose k-1}$

$= \dfrac{n}{k} {n-k-1 \choose k-1}$

Note that $f(n,k) \geq 0$ if and only if $k \leq \left \lfloor \dfrac{n}{2} \right \rfloor$ .

For the given problem, we have $n=12, k=5$ and thus the number of ways is $f(12,5) = \dfrac{12}{5} {6 \choose 4} = \boxed{36}$ .

12 × (12 – (2 × 4 + 1)) = 12 × 3 = 36