Gabarito disponível
Certa criança quer subir uma escada com 12 degraus, de modo a subir 1 ou 2 degraus de cada vez.
A partir dessa situação hipotética, assinale a opção que corresponde à quantidade de formas distintas que a criança poderá subir essa escada.
A partir dessa situação hipotética, assinale a opção que corresponde à quantidade de formas distintas que a criança poderá subir essa escada.
Resolução comentada
Contagem recursiva que gera a sequência de Fibonacci.
Seja a(n) o número de formas de subir n degraus. A última passada é de 1 ou 2 degraus, então a(n) = a(n−1) + a(n−2), com a(1) = 1 e a(2) = 2. Os valores são 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, e a(12) = 233.
Análise das alternativas
A) 12! conta permutações, e aqui não há ordenação de elementos distintos. B) 78 não resulta da recorrência. D) 792 é C(12,5), que ignora a soma de passos 1 e 2. E) 144 é a(11), um degrau a menos. C) Correta.
Referência: Análise combinatória – recorrência/Fibonacci
Resolução comentada do VaiConcursos.