Question

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 4 5, 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 1 5 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.

Devido a fileira ser espelhada, vamos considerar essas 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).

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. Isso resulta em seis possibilidades para os três últimos assentos, pois basta multiplicar o número de cadeiras restantes (3x2x1).

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$