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.
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
como o número de maneiras válidas de pintar um prédio de
andares sob as regras dadas.
Para montar uma solução contida em
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
andares restantes podem ser pintados de qualquer maneira válida: há 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
andares restantes podem ser pintados de qualquer maneira válida: há maneiras nesse caso.
Como os dois casos são disjuntos e cobrem todas as possibilidades, somamos as quantidades:
Esta é uma recorrência do tipo Fibonacci.
Passo 3
Precisamos das condições iniciais (casos pequenos) para determinar a sequência:
- Para
(um andar), as pinturas possíveis são: verde ou amarelo. Logo
- Para
(dois andares), vamos listar: , , . A opção é proibida. Logo
Com a recorrência
e os valores iniciais acima, podemos calcular
para qualquer
por somas sucessivas.
Passo 4
Agora calcular passo a passo para
e
(útil para a parte (a)):
Para conferir a conta e fixar a intuição, aqui estão explicitamente as
pinturas válidas para
. Use
para verde e
para amarelo:
(Confere-se que em nenhuma dessas aparece
consecutivo.)
Passo 5
Interpretação e ligação com Fibonacci (curtinha e prática): a sequência
satisfaz a mesma recorrência de Fibonacci e corresponde aos números de Fibonacci deslocados. Formalmente, escreve-se que
onde
é a sequência de Fibonacci com
. Não é necessário usar isso para calcular, mas é uma forma rápida de reconhecer valores já conhecidos.
Passo 6
Calculemos agora até
por somas sucessivas (para a parte (b)):
Resposta
a)
b)