Question

15. As 6 cadeiras de uma fila são numeradas de 1 a 6
e devem ser ocupadas uma de cada vez de modo que,
sempre que possível, é escolhida uma cadeira sem
vizinhas ocupadas.
Por exemplo, é válida a ordem de ocupação 1 6 3 2 45,
em que a primeira pessoa ocupa a cadeira 1, a segunda,
a cadeira 6, a terceira, a cadeira 3, a quarta, a cadeira 2,
a quinta, a cadeira 4 e a última, a cadeira 5. Já a ordem
15 2 3 6 4 não é válida, pois a terceira pessoa sentou-se
ao lado da primeira quando poderia ter se sentado em
uma cadeira sem vizinhas ocupadas. Quantas ordens de
ocupação válidas existem?​

Answer 1

Existem 192 ordens de ocupação válidas.

Inicialmente, veja que temos três possibilidades iniciais: a primeira escolha ser na ponta (1 e 6), nas posições intermediárias (2 e 5) ou no meio (3 e 4). Isso ocorre pois a fileira é espelhada.

Além disso, note que devemos escolher apenas as três primeiras opções de assentos, pois depois disso todas já vão ter vizinhos. Então, nos três últimos assentos, basta multiplicar o número de cadeiras restantes (3x2x1), resultando em 6 possibilidades.

Agora, veja também que, caso a primeira pessoa sente na ponta, restam quatro opções para a próxima. Então, temos dois caminhos: a segunda pessoa sentar no meio ou na ponta/intermediárias.

Caso sentar no meio, a terceira pessoa terá apenas uma opção (na outra ponta) e, a partir disso, temos as outras seis possibilidades calculadas anteriormente. Desse modo, o número de opções nesse caso será:

$4\times 1\times 6=24$

Contudo, caso aquela segunda pessoa não sentasse no meio, a terceira pessoa teria duas opções e, depois, restavam as seis possibilidades. Logo:

$4\times 2\times 6=48$

Agora, vamos analisar a sequência com a primeira pessoa sentando em uma das cadeiras intermediárias. Nesse caso, restam apenas duas opções para a segunda, pois em uma possível terceira opção seria inválida a partir da terceira pessoa. Então, seguindo assim, a terceira pessoa teria quatro opções. Então:

$2\times 4\times 6=48$

Por fim, vamos considerar que a primeira pessoa sentou no meio. Então, a segunda pessoa pode escolher a ponta mais próxima ou não. Caso escolha, a terceira pessoa tem duas opções. Assim:

$3\times 2\times 6=36$

Contudo, caso a segunda pessoa não escolha a ponta mais próxima, a terceira pessoa tem apenas uma opção, mas pode fazer isso de duas maneiras diferentes. Logo:

$2\times 3\times 1\times 6=36$

Por fim, basta somar todas as possibilidades, resultando no seguinte valor:

$48+24+48+36+36=192$