Postavljanje pravokutnika na pločice
Imate dvije zagonetke. Za pravokutnik dimenzija 1 x n, na koliko načina možete ispuniti ga mješavinom kvadrata 1 x 1 i pravokutnika 1 x 2? Za pravokutnik dimenzija 2 x n, na koliko načina možete ispuniti ga pravokutnicima 1 x 2?
IZAZOV
Zašto ove dvije zagonetke daju iste odgovore? Koji su odgovori kada su pravokutnici koji se popunjavaju dugi 10? Što je s onima koji su dugi 20?
ISTRAŽIVANJE
Po čemu su ova dva problema slična jedan drugome i ranijim zagonetkama? Kako se stvari mijenjaju u zagonetki 1 x n ako umjesto toga koristimo dijelove 1 x 1 i 1 x 3? Kako se stvari mijenjaju u zagonetki 1 x n ako koristimo dijelove 1 x 1, 1 x 2 i 1 x 3?
Bilješke
IZAZOV
Vidjeti kako primijeniti ranije rezultate na dio ili cijelu novu slagalicu je moćna vještina.
Ove dvije slagalice su potpuno iste prirode. Vertikalni dijelovi u pravokutniku 2 x n odgovaraju dijelovima 1 x 1 u pravokutniku 1 x n, a horizontalni dijelovi u pravokutniku 2 x n odgovaraju dijelovima 1 x 2 u pravokutniku 1 x n. Dakle, zapravo nema razlike između dvije slagalice.
Također, zagonetka s pravokutnikom 1 x n je potpuno ista kao zagonetka s koracima u "Fibonacci – 2". Korak po korak je kao da slažete kvadrat 1 puta 1, a dva koraka odjednom je kao da slažete pravokutnik 1 puta 2. Obje zagonetke su iste, pa su analiza i rezultati isti.
ISTRAŽIVANJE
Ako koristimo pravokutnike 1 puta 1 i 1 puta 3, mnogo se toga mijenja. Pogledajte prvih nekoliko vrijednosti i razmislite kako se izračunavaju. Za prvih nekoliko vrijednosti dobivamo 1, 1, 2, 3, 4, 6 i 9. Općenito, sljedeća vrijednost je zbroj trenutne vrijednosti i vrijednosti dva koraka prije nje. Dovoljno je jednostavno izračunati, ali to više nije Fibonnaccijev niz.
Ako koristimo 1 puta 1, 1 puta 2 i 1 puta 3, stvari se mijenjaju još dramatičnije. Sada je prvih nekoliko vrijednosti dano s 1, 2, 4, 7, 13 i 24. Sljedeća vrijednost u nizu je zbroj prethodne tri vrijednosti.
Nizovi poput ovog koji definiraju svoje sljedeće članove skupom formula koja uključuje prethodne članove nazivaju se rekurzivni nizovi. Fibonaccijevi brojevi nisu jedini rekurzivni niz, ali su vjerojatno najpoznatiji.