Problema
(Indicado a partir do 2º ano do E. M.)
(UFRJ-Adaptado) Uma pessoa pode subir uma escada da seguinte forma: a cada degrau,
- ou ela passa ao degrau seguinte
- ou galga dois degraus de uma só vez, pulando um degrau intermediário.
A exceção dessa regra ocorre somente se a pessoa estiver no penúltimo degrau, quando ela só terá a opção de passar para o último degrau.
Se [tex]P_{N}[/tex] é o número de modos diferentes que uma pessoa tem de subir uma escada de [tex]N[/tex] degraus dessa maneira, então:
a) Calcule [tex]P_{5}[/tex].
b) Determine [tex]N[/tex] tal que [tex]P_{N}=987[/tex].
Solução
a) Vamos listar todos as maneiras possíveis de subir uma escada com [tex]5[/tex] degraus, respeitando as restrições do enunciado.
- Subindo de degrau em degrau:
- [tex]1-2-3-4-5[/tex]
- Pulando um degrau:
- [tex]2-3-4-5[/tex]
- [tex]1-3-4-5[/tex]
- [tex]1-2-4-5[/tex]
- [tex]1-2-3-5[/tex]
- Pulando dois degraus:
- [tex]2-4-5[/tex]
- [tex]2-3-5[/tex]
- [tex]1-3-5[/tex]
Assim, temos [tex]\,\fcolorbox{black}{#eee0e5}{$8$}\,[/tex] maneiras diferentes.
b) Vamos voltar ao item anterior para tentar criar uma estratégia diferente da enumeração das soluções.
Imaginando uma escada com [tex]5[/tex] degraus temos dois casos a considerar:
1°) A pessoa começa pelo degrau de número [tex]1[/tex].
2°) A pessoa começa pelo degrau de número [tex]2[/tex].
Perceba que esses dois casos são excludentes.
- Se a pessoa começa pelo degrau de número [tex]1[/tex], para continuar subindo ela tem um "novo" problema com as mesmas restrições do anterior, porém agora a escada possui [tex]4[/tex] degraus.
Assim, segundo o enunciado, ela terá [tex]P_{4}[/tex] maneiras de subir a escada com quatro degraus. - Se a pessoa começa pelo degrau de número [tex]2[/tex], para continuar a subida ela terá um "novo" problema com as mesmas restrições do anterior, porém agora a escada possui [tex]3[/tex] degraus.
Logo, de acordo com o enunciado, ela tem [tex]P_{3}[/tex] maneiras de subi-la.
Com isso, podemos perceber que o número de modos de resolver o problema para [tex]5[/tex] degraus é a soma das soluções de uma escada com [tex]4[/tex] degraus com as soluções de uma escada com [tex]3[/tex] degraus. Em símbolos, [tex]P_{5}=P_{4}+P_{3}[/tex].
Podemos generalizar essa ideia para uma escada com [tex]N[/tex] degraus e concluir que:
[tex]\qquad \qquad \boxed{P_{N}=P_{N-1}+P_{N-2}}. \qquad \qquad \textcolor{#800000}{(i)}[/tex]
Como [tex]P_{1}=1[/tex](número de maneiras de subir uma escada com apenas um degrau) e [tex]P_{2}=2[/tex] (número de maneiras de subir uma escada com dois degraus), podemos utilizar a relação [tex]\textcolor{#800000}{(i)}[/tex] e construir uma sequência numérica até encontrarmos o [tex]N[/tex] desejado.
[tex]\qquad \qquad P_{1}=1\\
\qquad \qquad P_{2}=2\\
\qquad \qquad P_{3}=3\\
\qquad \qquad P_{4}=5\\
\qquad \qquad P_{5}=8\\
\qquad \qquad P_{6}=13\\
\qquad \qquad P_{7}=21\\
\qquad \qquad P_{8}=34\\
\qquad \qquad P_{9}=55\\
\qquad \qquad P_{10}=89\\
\qquad \qquad P_{11}=144\\
\qquad \qquad P_{12}=233\\
\qquad \qquad P_{13}=377\\
\qquad \qquad P_{14}=610\\
\qquad \qquad P_{15}=\boxed{987}\,.[/tex]
Portanto, [tex]\,\fcolorbox{black}{#eee0e5}{$N=15$}\,.[/tex]
Na resolução deste problema utilizamos o que a Matemática denomina de raciocínio recursivo. Para aprender mais sobre essa técnica visite a Sala de Estudo sobre Recorrências do nosso Blog.
Solução elaborada pelos Moderadores do Blog.