OBMEP 2019 | Nível 3 (Ensino Médio)

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?