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

Passo 1

O enunciado dá um muro com 5 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 n faixas pelo número de faixas não-azuis consecutivas que aparecem no final:
an = número de pinturas de (n) faixas terminando com 0 não-azuis (ú<ima é azul), úãúé
bn = número de pinturas de (n) faixas terminando com 1 não-azul, úã
cn = número de pinturas de (n) faixas terminando com 2 não-azuis úã
O total de pinturas de n faixas válidas é
Tn = an + bn + cn

Passo 3

Para estender uma pintura de n para n+1 faixas, temos duas possibilidades na faixa nova:
  1. Pintar de azul: isso zera o contador de não-azuis, e pode vir de qualquer estado.
  2. 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
an+1 = an + bn + cn, bn+1 = 2,an, cn+1 = 2,bn
Aqui multiplicamos por 2 no caso não-azul porque há duas escolhas (vermelha ou branca).

Passo 4

Agora calculamos de n=0 até n=5. Para n=0 (sequência vazia) temos
a0 = 1, b0 = 0, c0 = 0, T0 = 1
Usando as recursões:
Para n=1:
a1 = T0 = 1, b1 = 2,a0 = 2, c1 = 2,b0 = 0, T1 = 1 + 2 + 0 = 3
Para n=2:
a2 = T1 = 3, b2 = 2,a1 = 2cdot1 = 2, c2 = 2,b1 = 2cdot2 = 4, T2 = 3 + 2 + 4 = 9
Para n=3:
a3 = T2 = 9, b3 = 2,a2 = 2cdot3 = 6, c3 = 2,b2 = 2cdot2 = 4, T3 = 9 + 6 + 4 = 19
Para n=4:
a4 = T3 = 19, b4 = 2,a3 = 2cdot9 = 18, c4 = 2,b3 = 2cdot6 = 12, T4 = 19 + 18 + 12 = 49
Para n=5:
a5 = T4 = 49, b5 = 2,a4 = 2cdot19 = 38, c5 = 2,b4 = 2cdot18 = 36, T5 = 49 + 38 + 36 = 123

Passo 5

O número de maneiras distintas de pintar as 5 faixas respeitando a condição é
T5 = 123

Resposta

123

Exercícios relacionados