Flisebelægning af rektangler
Du har to gåder. For et 1 gange n rektangel, på hvor mange måder kan du fylde det med en blanding af 1 gange 1 firkanter og 1 gange 2 rektangler? For et 2 gange n rektangel, på hvor mange måder kan du fylde det med 1 gange 2 rektangler?
UDFORDRINGEN
Hvorfor giver disse to gåder de samme svar? Hvad er svarene, når de udfyldte rektangler er 10 lange? Hvad med når de er 20 lange?
UDFORSKNING
Hvordan ligner disse to problemer hinanden og tidligere gåder? Hvordan ændrer tingene sig i 1 gange n-gåden, hvis vi bruger 1 gange 1 og 1 gange 3 brikker i stedet? Hvordan ændrer tingene sig i 1 gange n-gåden, hvis vi bruger 1 gange 1, 1 gange 2 og 1 gange 3 brikker?
Noter
UDFORDRINGEN
At se, hvordan man anvender tidligere resultater på dele af eller hele et nyt puslespil, er en stærk færdighed.
Disse to puslespil er præcis ens af natur. Lodrette brikker i 2 x n-rektanglet svarer til 1 x 1 brikker i 1 x n-rektanglet, og vandrette brikker i 2 x n-rektanglet svarer til 1 x 2 brikker i 1 x n-rektanglet. Så der er egentlig ingen forskel mellem de to puslespil.
1 x n rektangel-puslespillet er også præcis som trin-puslespillet i "Fibonacci - 2". At gå et skridt ad gangen er som at lægge et 1 x 1-felt, og at gå to skridt ad gangen er som at lægge et 1 x 2-rektangel. De to puslespil er ens, så analysen og resultaterne er de samme.
UDFORSKNING
Hvis vi bruger rektangler på 1 gange 1 og 1 gange 3, ændrer der sig meget. Se på de første par værdier, og overvej, hvordan de beregnes. Vi får 1, 1, 2, 3, 4, 6 og 9 for de første par værdier. Generelt er den næste værdi summen af den aktuelle værdi og den to trin før. Det er simpelt nok at beregne, men det er ikke længere Fibonnaci-sekvensen.
Hvis vi bruger 1 gange 1, 1 gange 2 og 1 gange 3, ændrer tingene sig endnu mere dramatisk. Nu er de første par værdier givet ved 1, 2, 4, 7, 13 og 24. Den næste værdi i sekvensen er summen af de foregående tre værdier.
Følger som denne, der definerer deres næste led ved hjælp af en formel, der involverer foregående led, kaldes rekursive følger. Fibonacci-tallene er ikke den eneste rekursive følge, men de er nok de mest berømte.