Doze cavaleiros estão sentados em torno de uma mesa redonda. Cada um dos doze cavaleiros considera seus dois vizinhos como rivais.Deseja-se formar um grupo de cinco cavaleiros para libertar uma princesa, sendo que nesse grupo não poderá haver cavaleiros rivais. Determine de quantas maneiras é possível escolher esse grupo.

Passo 1

O enunciado diz que há doze cavaleiros dispostos em círculo e que dois cavaleiros são rivais se estiverem sentados lado a lado. Queremos escolher um grupo de cinco cavaleiros sem jamais ter dois rivais no mesmo grupo. Esse é um problema de contagem de subconjuntos de tamanho fixo em um ciclo de n=12 vértices, proibindo vértices adjacentes.

Passo 2

Para contar essas escolhas, fixamos uma posição especial (digamos o cavaleiro na “cadeira” 1) e dividimos em dois casos mutuamente exclusivos: ou o cavaleiro 1 não é escolhido, ou ele é escolhido. Isso elimina a complicação do vínculo circular e nos leva a problemas de linha.

Passo 3

Caso 1: o cavaleiro 1 não é escolhido.
Então só restam os cavaleiros de 2 até 12 sentados em linha, total de 11 vagas, e precisamos escolher 5 sem dois adjacentes numa linha. O número de formas é dado por
\binom{11 - 5 + 1}{5} \;=\;\binom{7}{5}\;=\;21.

Passo 4

Caso 2: o cavaleiro 1 é escolhido.
Como 1 está no grupo, seus vizinhos (cadeiras 12 e 2) não podem ser escolhidos. Sobram então as cadeiras de 3 até 11, ou seja, 9 vagas em linha, nas quais precisamos escolher os outros 4 cavaleiros sem adjacências. O total é
\binom{9 - 4 + 1}{4} \;=\;\binom{6}{4}\;=\;15.

Passo 5

Somando as duas possibilidades, o número total de grupos de cinco cavaleiros sem rivais é
21 + 15 = 36.

Resposta

O número de maneiras possíveis é 36.

Exercícios relacionados