De quantas formas diferentes um sapo sobe 11 degraus?

Question

Suponha que um sapo está no térreo e quer subir 11 degraus. Ele sobe de um em um degrau ou de dois em dois degraus. De quantas formas diferentes ele sobre esses 11 degraus?

Answer 1

Utilizando análise combinatória, temos que podem ocorrer qualquer combinação de pulos de 1 e 2 degraus que no final somem 11. Representado o pulo de um degrau por I e o de dois degraus por II, as possibilidades são:
I - 11 | II - 0 = 11!/11! = 1 possibilidade
I - 9 | II - 1 = 10!/(9! 1!) = 10 possibilidades
I - 7 | II - 2 = 9! /(7! 2!) = 36 possibilidades
I - 5 | II - 3 = 8!/(5! 3!) = 56 possibilidades
I - 3 | II - 4 = 7!/(3! 4!) = 35 possibilidades
I - 1 | II - 5 = 6!/(5! 1!) = 6 possibilidades

No total: 144 possibilidades
Ou como dito na resposta anterior, o 11º termo na Sequência de Fibonacci, começando a partir do segundo 1.

Comments

Legal! Obrigado!

Answer 2

Possivelmente, esse problema pode ser resolvido usando Análise Combinatória (talvez outra pessoa possa apresentar essa solução). Mas note que a solução abaixo é simples e muito intuitiva.

Para ir para o degrau 1 existe apenas uma possibilidade. Logo, o número de possibilidades é igual a 1.

Para ir para o degrau 2 existem duas possibilidades: dando 1 salto de tamanho 2 do degrau zero ou dando 1 salto de tamanho 1 do degrau 1. Logo o número de possibilidades é igual 1+1=2.

Para ir para o degrau 3 existem duas possibilidades: dando 1 salto de tamanho 1 do degrau 2 ou dando um salto de tamanho 2 do degrau 1. Logo o número de possibilidades é igual 2+1=3.

Ou seja, para qualquer degrau \(n\gt 1\), existem duas possibilidades ou vindo do degrau anterior, onde foram possíveis \(x_{n-1}\) formas diferentes, ou do degrau anterior, onde foram possíveis \(x_{n-2}\) formas diferentes. Logo, para se chegar ao degrau são necessárias \(x_{n}=x_{n-1}+x_{n-2}\) soluções possíveis que é justamente a sequência de Fibonacci.