Combinatória

Doze cavaleiros estão sentados em torno de uma mesa redonda. Cada um
dos 12 cavaleiros considera seus dois vizinhos como rivais. Deseja-se formar um grupo de
5 cavaleiros para salvar uma princesa. Nesse grupo não poderá haver cavaleiros rivais.
Determine de quantas maneiras é possível escolher esse grupo.

Já estudou o segundo lema de Laplansky? É só aplicá-lo. Sem ele, fica um pouco mais complicado. Tens o gabarito aí?

Pense num relógio de ponteiros de 1 a 12

Imagine que o cavaleiro 1 é escolhido (2 e 12 são descartados)

E assim por diante

Eis as possibilidades, com os escolhidos em preto, os não escolhidos em azul, e os descartados em vermelho

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8  - 9 - 10 - 11 - 12

Com isto completamos os grupos em que 1 faz parte
Agora retira-se 1 e começa escolhendo 2
E assim por diante

Creio que o senhor tenha esquecido das possibilidades 1 3 5 8 10 e 1 3 5 8 11.

Pesquisei na internet e vi que o gab é 36,entretanto chego a 32, o que posso ter feito de errado?
1 3 5 7 9
1 3 5 7 10
1 3 5 7 11
1 3 5 8 10
1 3 5 8 11
1 3 5 9 11
1 3 6 8 10
1 3 6 8 11
1 3 6 9 11
1 3 7 9 11
1 4 6 8 11
1 4 6 8 10
1 5 7 9 11
2 4 6 8 10
2 4 6 8 11
2 4 6 8 12
2 4 6 9 11
2 4 6 9 12
2 4 6 10 12
2 4 7 9 12
2 4 8 10 12
2 5 7 9 11
2 5 7 9 12
2 5 8 10 12
2 6 8 10 12
3 5 7 9 11
3 5 7 9 12
3 5 7 10 12
3 5 8 10 12
3 6 8 10 12
4 6 8 10 12

É inviável fazer isso listando possibilidades. A resposta é imediata utilizando o segundo lema que citei e foi ignorado: 12/(12-5)*C(12-5,5) = 36.

Ainda não havia estudado a respeito do lema, pesquisei sobre o mesmo e já consegui resolver.
Obrigado novamente!

Para quem tiver interesse:

Seja n a quantidade de cavaleiros,podemos denominar os escolhidos por +'s, os não escolhidos por -'s, o número de escolhas por p, o número total de elementos por n com isso podemos formular:

+++....------ onde o número de +'s é p, e o número de -'s é n-p

agora seja 0's os espaços vazios temos então:

0-0-0-0-0-0-0....0-0 onde se tem que o número de -'s é n-p e o número de espaços vazios é n-p+1,dos n-p+1 espaços vazios devemos escolher p deles.
no entanto, por este método estamos contanto também o caso em que escolhemos o primeiro e o último e devemos remover, então de n-p-1(desconta-se o primeiro e o último espaço) devemos escolher p-2 espaços vazios.
logo temos que para um caso em geral, o número de cavaleiros é:

(n-p+1)!/(p!*[n-2*p+1]) - (n-p-1)!/([p-2]!*[n-2*p+1]!)

Para o caso do enunciado:
N=12 P=5
(12-5+1)!/(5!*[12-10+1]!) - (12-5-1)!/([3]!*[12-2*5+1]!) =

8!/(5!*3!) - 6!/(3!*3!) =
8*7 - 5 * 4 = 36