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
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
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
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 é
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 é
Passo 5
Somando as duas possibilidades, o número total de grupos de cinco cavaleiros sem rivais é
Resposta
O número de maneiras possíveis é
.