OBMEP 2019: As 6 cadeiras de uma fila são numeradas de 1 a 6 e devem ser ocupadas uma de cada vez

OBMEP 2019: 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, é escolh...

OBMEP 2019: 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?

A) 72
B) 108
C) 144
D) 192
E) 216

QUESTÃO ANTERIOR:
- OBMEP 2019: Quatro cartões, cada um deles com um número inteiro positivo, são tais que toda vez que somamos os números de três deles obtemos um número igual ou maior do que 24.

RESOLUÇÃO:
A ocupação dos lugares se dá em duas etapas:

* Inicialmente, os lugares são ocupados de modo que não haja cadeiras vizinhas ocupadas, até que isto não seja mais possível.

* A seguir, os demais lugares são ocupados em qualquer ordem.

Para contar o número de possibilidades de ocupação, vamos, inicialmente, encontrar as configurações maximais, para as quais não há cadeiras vizinhas ocupadas, mas tais que o próximo a chegar necessariamente precisará sentar ao lado de alguém. Há dois tipos de configurações maximais:

* Com 2 pessoas, que devem ocupar os lugares 2 e 5

* Com 3 pessoas, que podem ocupar os lugares 1, 3, 5; 1, 3, 6; 1, 4, 6; ou 2, 4, 6.

No primeiro caso, há 2 possibilidades para a ordem de ocupação dos assentos 2 e 5; para cada uma dessas possibilidades os lugares podem ser ocupados em qualquer ordem, ou seja, há 4 x 3 x 2 x 1 = 24 possibilidades.

Para cada uma das 4 situações do segundo caso, há 3 x 2 x 1 = 6 possibilidades de ordem de ocupação dos lugares da configuração maximal; a seguir, para cada uma dessas possibilidades, os demais lugares também podem ser ocupados em qualquer ordem, com um total de 3 x 2 x 1 = 6 possibilidades.

Logo, o número total de possibilidades de ocupação é igual a: 2 x 24 + 4 x 6 x 6 = 192 possibilidades.

GABARITO:
D) 192

PRÓXIMA QUESTÃO:
- OBMEP 2019: A rã Zinza quer ir da pedra 1 até a pedra 10 em cinco pulos, pulando de uma pedra para a seguinte ou por cima de uma ou de duas pedras. De quantas maneiras diferentes Zinza pode fazer isso?

Questão disponível em:
- Questões OBMEP 2019 com Gabarito e Resolução