Kalle Kanin

En interessant oppgave fra Abelkonkurranse 2018-2019  :

Kalle kanin skal hoppe opp en trapp som har 12 trinn. Han hopper enten ett eller to trinn av gangen, og han hopper aldri ned igjen. På hvor mange måter kan han hoppe til toppen av trappen?

*** Tenk gjennom før du leser videre ***

La oss se på hvordan Kalle kanin kan komme seg til øverste trinn (trinn 12) av trappen. Gitt begrensningen at Kalle kun kan hoppe opp ett eller to trinn av gangen, er det kun to måter å hoppe dit; enten fra trinn 11 eller fra trinn 10.

Anta at antall mulige måter å komme frem til trinn 12 er a₁₂ . Da vil:

a₁₂ = a₁₁ + a₁₀

hvor a₁₁ er antall måter å komme seg til trinn 11 og a₁₀ er antall måter å komme seg til trinn 10.

For eksempel, hvis det er fem måter å hoppe opp til trinn 10, og åtte måter å hoppe opp til trinn 11, vil det være det totale antall måter å hoppe til trinn 12 være: 5+8 = 13. Men hvor mange måter er det virkelig å komme frem til trinn 11 på? Ved bruk av samme logikk som for trinn 12 kan vi konkludere: a₁₁ = a₁₀ + a₉ , og på samme måte for trinn 10: a₁₀ = a₉ + a₈ . Den samme prosedyren kan vi følge helt til trinn 1, hvor vi ser at det bare er en mulighet: a₁ = 1, mens det er to muligheter å hoppe opp til trinn 2 dvs. a₂ = 2 . Vi kan nå regne ut antall måter å hoppe opp til trinn 3 ved å legge sammen: 1+2 = 3. Deretter kan vi repetere denne prosessen til vi ender opp med a₁₂ = 233. Denne typen følge, hvor hvert ledd er lik summen av de to foregående leddene, er en del av det vi kaller Fibonacci-tallfølgen, som har stor betydning i matematikkens historie.

Ved programmering er det lettvint å generere Fibonacci-følgen. Her er et forslag til Python-kode som genererer en del av Fibonacci-følge med N ledd, og som spesifikt for denne oppgaven genererer en slik følge med 12 ledd, hvor hvert ledd representerer antall måter å hoppe til det korresponderende trinnet i trappen: 

def fibonacci(N):
    x = [0]* N
    x[0] = 1
    x[1] = 2
    for n in range(2,N):
        x[n] = x[n-1]+x[n-2]
    return x

print fibonacci(12) 

***resultat***
[  1   2   3   5   8  13  21  34  55  89 144 233]

***

En annen fremgangsmåte basert på Magne Myran sin forklaring med anvendelse av kombinatorikk (se kommentar):