Doce caballeros están sentados alrededor de una mesa redonda. Cada caballero desconfía de los dos que están sentados a sus lados, pero no de los otros nueve. Se debe formar un grupo de tres caballeros para ir a rescatar a una princesa, de tal modo que ninguno de ellos desconfíe de alguno de los otros dos. ¿De cuántas maneras se puede formar el grupo?
Partamos de un caballero y llamémoslos $a_1,a_2,\ldots,a_{12}$ en sentido horario, y miremos los subíndices en módulo $12$. Un caballero $a_n$ desconfía de otro $a_m$ si $n$ y $m$ son números consecutivos.
La cantidad de formas de elegir $3$ caballeros es $\binom{12}{3}=220$. Vamos a restarle los casos en los que hay caballeros que desconfían de otros.
Si los $3$ caballeros son consecutivos $a_i,a_{i+1},a_{i+2}$ miremos a $a_i$. Puede ser cualquiera de los $12$ caballeros, por lo que hay $12$ posibilidades.
Si hay $2$ caballeros consecutivos y otro que no, razonando igual que antes hay $12$ maneras de elegir los primeros, y para el otro podemos elegir cualquiera que no sean los $2$ elegidos y sus vecinos, es decir $12-2-2=8$ maneras. En total son $12\cdot8=96$ posibilidades.
Finalmente tenemos $220-12-96=112$ maneras de formar el grupo. $\bigstar$