Problema20
Letícia vai pintar um muro dividido em 5 faixas horizontais, utilizando três cores: azul, vermelha e branca. Ela quer garantir que, em toda sequência de três faixas consecutivas, pelo menos uma delas esteja pintada de azul.
De quantas maneiras distintas Letícia pode pintar o muro, respeitando essa condição?
54
81
- 96
- 108
- 123
De quantas maneiras distintas Letícia pode pintar o muro, respeitando essa condição?
81
Passo 1
O enunciado dá um muro com
faixas horizontais e três cores disponíveis: azul, vermelha e branca. A condição é que, em qualquer sequência de três faixas consecutivas, apareça pelo menos uma azul. Em outras palavras, não podemos ter três faixas seguidas todas não-azuis (isto é, vermelha ou branca). O conteúdo aqui é contar sequências sujeitas a uma restrição de evitar um certo padrão, o que faremos com recursão (programação dinâmica simples).
Passo 2
Vamos classificar as pinturas de
faixas pelo número de faixas não-azuis consecutivas que aparecem no final:
O total de pinturas de
faixas válidas é
Passo 3
Para estender uma pintura de
para
faixas, temos duas possibilidades na faixa nova:
- Pintar de azul: isso zera o contador de não-azuis, e pode vir de qualquer estado.
- Pintar de não-azul (2 opções: vermelha ou branca): só é permitido se o estado anterior tiver menos de 2 não-azuis consecutivas.
Logo as recursões são
Aqui multiplicamos por 2 no caso não-azul porque há duas escolhas (vermelha ou branca).
Passo 4
Agora calculamos de
até
. Para
(sequência vazia) temos
Usando as recursões:
Para
:
Para
:
Para
:
Para
:
Para
:
Passo 5
O número de maneiras distintas de pintar as
faixas respeitando a condição é
Resposta
123