Questão 5 (Nível 2) da 2ª fase da OBMEP 2019

Question

Dizemos que uma fila de cadeiras de cinema está ocupada de forma quase-cheia quando não há duas cadeiras consecutivas ocupadas, mas a próxima pessoa a chegar será obrigada a sentar-se ao lado de uma cadeira já ocupada. Uma fila de 5 cadeiras tem exatamente quatro ocupações quase-cheias, mostradas abaixo. As cadeiras marcadas com X indicam que elas estão ocupadas.

Fila de 5 cadeiras com a 1ª, 3ª e 5ª cadeiras ocupadas com X
Fila de 5 cadeiras com a 1ª e 4ª cadeiras ocupadas com X
Fila de 5 cadeiras com a 2ª e 4ª cadeiras ocupadas com X

a) Uma fila de 6 cadeiras possui cinco ocupações quase-cheias. Marque com X as cadeiras dessas ocupações.

Fila com 6 cadeiras desocupadas

b) Quantas são as ocupações quase-cheias em uma fila de 8 cadeiras em que a segunda cadeira já está ocupada?

Fila de 8 cadeiras com a segunda cadeira ocupada com X

c) A tabela abaixo apresenta o número de ocupações quase-cheias para algumas filas de cadeiras. Calcule o total de ocupações quase-cheias em uma fila com 19 cadeiras. Justifique.

Número de cadeiras da fila	5	6	...	16	17	18	19
Número de ocupações quase-cheias	4	5	...	86	114	151

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 5 (Nível 2) da 2ª fase da OBMEP 2019

Nível 2 · Matemática: Princípio fundamental da contagem

Dizemos que uma fila de cadeiras de cinema está ocupada de forma quase-cheia quando não há duas cadeiras consecutivas ocupadas, mas a próxima pessoa a chegar será obrigada a sentar-se ao lado de uma cadeira já ocupada. Uma fila de 5 cadeiras tem exatamente quatro ocupações quase-cheias, mostradas abaixo. As cadeiras marcadas com X indicam que elas estão ocupadas.

Fila de 5 cadeiras com a 1ª, 3ª e 5ª cadeiras ocupadas com X
Fila de 5 cadeiras com a 1ª e 4ª cadeiras ocupadas com X
Fila de 5 cadeiras com a 2ª e 4ª cadeiras ocupadas com X

a) Uma fila de 6 cadeiras possui cinco ocupações quase-cheias. Marque com X as cadeiras dessas ocupações.

Fila com 6 cadeiras desocupadas

b) Quantas são as ocupações quase-cheias em uma fila de 8 cadeiras em que a segunda cadeira já está ocupada?

Fila de 8 cadeiras com a segunda cadeira ocupada com X

c) A tabela abaixo apresenta o número de ocupações quase-cheias para algumas filas de cadeiras. Calcule o total de ocupações quase-cheias em uma fila com 19 cadeiras. Justifique.

Número de cadeiras da fila	5	6	...	16	17	18	19
Número de ocupações quase-cheias	4	5	...	86	114	151

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a) [Figura: cinco configurações de seis cadeiras alinhadas, com algumas ocupadas com "X": na primeira, as cadeiras 1, 3 e 5 estão ocupadas; na segunda, as cadeiras 1, 3 e 6; na terceira, as cadeiras 1, 4 e 6; na quarta, as cadeiras 2, 4 e 6; na quinta, as cadeiras 2 e 5.]

b) Como a segunda cadeira já está ocupada, a primeira e terceira cadeiras necessariamente devem ficar livres. Assim, os demais a chegar devem ocupar, de modo quase cheio, as 5 cadeiras restantes. Como visto no enunciado, há 4 possibilidades para a ocupação dessas cadeiras. [Figura: fileira de 8 cadeiras com a segunda ocupada por "X" e uma linha vertical tracejada separando as 3 primeiras cadeiras das 5 restantes]

c) Vamos enumerar as cadeiras em ordem crescente. Em uma ocupação quase cheia de 19 cadeiras, exatamente uma das duas primeiras cadeiras deve estar ocupada.

Com a primeira cadeira ocupada (e, em consequência, a segunda livre), as demais pessoas devem ocupar, de modo quase cheio, as outras 17 cadeiras. De acordo com a tabela, há 114 possibilidades para essa ocupação.

[Figura: faixa com 19 compartimentos numerados de 1 a 19, onde a posição 2 está destacada com "X", e uma linha vertical tracejada divide as posições 3 e 4]

Com a segunda cadeira ocupada (e, em consequência, as duas ao lado livres), as demais pessoas devem ocupar, de modo quase cheio, as outras 16 cadeiras. De acordo com a tabela, há 86 possibilidades para essa ocupação. Portanto, há um total de 114 + 86 = 200 ocupações quase cheias para 19 cadeiras.

[Figura: faixa com 19 compartimentos numerados de 1 a 19, onde a posição 1 está destacada com "X", e uma linha vertical tracejada divide as posições 2 e 3]

Observação: A quantidade a_n de ocupações quase cheias de n cadeiras é dada pela recorrência a_1 = 1, a_2 = 2, a_3 = 2 e a_n = a_{n-2} + a_{n-3} , para todo n \ge 4.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Numere as cadeiras de 1 a 6. Em cada ocupação não pode haver duas cadeiras vizinhas ocupadas, e cada cadeira vazia precisa ter um vizinho ocupado, senão a próxima pessoa se sentaria ali sem ficar ao lado de ninguém.

Separe pela primeira cadeira ocupada, que é a 1 ou a 2:

Começando na 1, a 2 fica vazia. Para a 3 há duas possibilidades.
- Com a 3 ocupada, a 4 fica vazia e restam a 5 ou a 6 ocupadas: \{1,3,5\} e \{1,3,6\}.
- Com a 3 vazia, a 4 precisa estar ocupada, e então a 6 também: \{1,4,6\}.
Começando na 2, a 1 e a 3 ficam vazias. Para a 4 há duas possibilidades.
- Com a 4 ocupada, a 6 também precisa estar: \{2,4,6\}.
- Com a 4 vazia, a 5 precisa estar ocupada: \{2,5\}.

São as cinco ocupações, e todas foram conferidas. Marque X nas cadeiras:

1, 3 e 5
1, 3 e 6
1, 4 e 6
2, 4 e 6
2 e 5

Resposta: X nas cadeiras {1,3,5}, {1,3,6}, {1,4,6}, {2,4,6} e {2,5}.

b) Com a cadeira 2 ocupada, as cadeiras 1 e 3 ficam vazias, e as duas já têm um vizinho ocupado (a 2). Nenhuma delas precisa de mais nada.

Sobram as cadeiras de 4 a 8, que formam uma fila de 5 cadeiras. A cadeira 4 pode ser ocupada, porque a 3 está vazia. Se a 4 ficar vazia, ela precisa de um vizinho ocupado, e esse só pode ser a 5, pois a 3 está vazia. Portanto essa fila de 5 cadeiras segue exatamente as mesmas regras de uma fila isolada.

O enunciado diz que uma fila de 5 cadeiras tem 4 ocupações quase-cheias.

Resposta: 4 ocupações.

c) Seja a_n o número de ocupações quase-cheias de uma fila de n cadeiras. Veja onde está a primeira pessoa:

Se for na cadeira 1, a 2 fica vazia e a fila das cadeiras 3,\dots,n (com n-2 cadeiras) se comporta como uma fila isolada, como no item (b). Há a_{n-2} ocupações.
Se for na cadeira 2, a 1 e a 3 ficam vazias e a fila das cadeiras 4,\dots,n (com n-3 cadeiras) se comporta como uma fila isolada. Há a_{n-3} ocupações.

As duas situações não se misturam e esgotam todos os casos. Logo:

a_n=a_{n-2}+a_{n-3}

Conferindo com os dados da tabela: a_8=a_6+a_5=5+4=9, e a_{17}=a_{15}+a_{14}=65+49=114. Os valores intermediários, pela mesma regra, são a_{14}=49, a_{15}=65 e a_{16}=86, que coincide com a tabela.

Para 19 cadeiras, use a_{19}=a_{17}+a_{16}:

a_{19}=114+86=200

Resposta: 200 ocupações.

Assunto: Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 5 no caderno Nível 2 da 2ª fase da OBMEP 2019

Fonte: OBMEP 2ª fase 2019 · Nível 2. Prova oficial ↗