Questão 21 (PROFMAT-MA12-AV3/2014). Resolva os problemas:
a) Imagine que um prédio de quatro andares deva ser pintado usando-se uma cor para cada andar. Sabendo que as cores utilizadas podem ser verde e amarelo e que andares consecutivos não poderão ser pintados de amarelo, de quantas maneiras é possível fazer a pintura deste prédio?
b) Resolva o mesmo problema para um prédio de 10 andares.

Passo 1

O enunciado pede duas contagens separadas, usando somente as cores verde e amarelo e com a restrição de que andares consecutivos não podem ser pintados de amarelo. Mais precisamente:
  • (a) Quantas maneiras de pintar um prédio de quatro andares com essas regras?
  • (b) Quantas maneiras de pintar um prédio de dez andares com essas regras?
Informações relevantes dadas:
  • As cores disponíveis são exatamente duas: verde e amarelo.
  • Não é permitido ter dois andares consecutivos pintados de amarelo.
  • Cada andar recebe exatamente uma cor.
  • Deve-se contar o número total de pinturas possíveis, obedecendo a restrição.

Passo 2

Vamos organizar a contagem de forma sistemática. Defina a_n como o número de maneiras válidas de pintar um prédio de n andares sob as regras dadas.
Para montar uma solução contida em n andares, olhe para a cor do primeiro andar (o de cima ou o de baixo — a escolha do “primeiro” é apenas para raciocinar, o resultado é o mesmo). Há dois casos exclusivos e cobrem todas as possibilidades:
  • Se o primeiro andar for verde, então os n-1 andares restantes podem ser pintados de qualquer maneira válida: há a_{n-1} maneiras nesse caso.
  • Se o primeiro andar for amarelo, então o segundo andar obrigatoriamente não pode ser amarelo (pela restrição), portanto o segundo tem que ser verde. Depois desses dois andares fixos (amarelo, verde), os n-2 andares restantes podem ser pintados de qualquer maneira válida: há a_{n-2} maneiras nesse caso.
Como os dois casos são disjuntos e cobrem todas as possibilidades, somamos as quantidades:
a_n = a_{n-1} + a_{n-2}.
Esta é uma recorrência do tipo Fibonacci.

Passo 3

Precisamos das condições iniciais (casos pequenos) para determinar a sequência:
  • Para n=1 (um andar), as pinturas possíveis são: verde ou amarelo. Logo
a_1 = 2.
  • Para n=2 (dois andares), vamos listar: GG, GA, AG. A opção AA é proibida. Logo
a_2 = 3.
Com a recorrência a_n=a_{n-1}+a_{n-2} e os valores iniciais acima, podemos calcular a_n para qualquer n por somas sucessivas.

Passo 4

Agora calcular passo a passo para n=3 e n=4 (útil para a parte (a)):
  • a_3 = a_2 + a_1 = 3 + 2 = 5.
  • a_4 = a_3 + a_2 = 5 + 3 = 8.
Para conferir a conta e fixar a intuição, aqui estão explicitamente as 8 pinturas válidas para n=4. Use G para verde e A para amarelo:
GGGG,\\ GGGA,\\ GGAG,\\ GAGG,\\ GAGA,\\ AGGG,\\ AGGA,\\ AGAG.
(Confere-se que em nenhuma dessas aparece AA consecutivo.)

Passo 5

Interpretação e ligação com Fibonacci (curtinha e prática): a sequência a_1=2,\\ a_2=3,\\ a_3=5,\\ a_4=8,\dots satisfaz a mesma recorrência de Fibonacci e corresponde aos números de Fibonacci deslocados. Formalmente, escreve-se que
a_n = F_{n+2},
onde (F_k) é a sequência de Fibonacci com F_1=1,\\ F_2=1. Não é necessário usar isso para calcular, mas é uma forma rápida de reconhecer valores já conhecidos.

Passo 6

Calculemos agora até n=10 por somas sucessivas (para a parte (b)):
\begin{aligned} a_5 &= a_4 + a_3 = 8 + 5 = 13,\\\ a_6 &= a_5 + a_4 = 13 + 8 = 21,\\\ a_7 &= a_6 + a_5 = 21 + 13 = 34,\\\ a_8 &= a_7 + a_6 = 34 + 21 = 55,\\\ a_9 &= a_8 + a_7 = 55 + 34 = 89,\\\ a_{10} &= a_9 + a_8 = 89 + 55 = 144. \end{aligned}

Resposta

a) 8
b) 144

Exercícios relacionados