Układanie prostokątów
Masz dwie łamigłówki. Na ile sposobów możesz wypełnić prostokąt o wymiarach 1 na n kwadratami o wymiarach 1 na 1 i prostokątami o wymiarach 1 na 2? Na ile sposobów możesz wypełnić prostokąt o wymiarach 2 na n prostokątami o wymiarach 1 na 2?
WYZWANIE
Dlaczego te dwie łamigłówki dają te same odpowiedzi? Jakie są odpowiedzi, gdy wypełniane prostokąty mają długość 10? A co, gdy mają długość 20?
POSZUKIWANIE
Na czym polega podobieństwo tych dwóch problemów do siebie i wcześniejszych łamigłówek? Jak zmieni się układanka 1 na n, jeśli zamiast tego użyjemy elementów 1 na 1 i 1 na 3? Jak zmieni się układanka 1 na n, jeśli użyjemy elementów 1 na 1, 1 na 2 i 1 na 3?
Komentarz
WYZWANIE
Umiejętność zastosowania wcześniejszych wyników do części lub całości nowej układanki jest potężną umiejętnością.
Te dwie łamigłówki są identyczne. Pionowe elementy w prostokącie 2xn odpowiadają elementom 1x1 w prostokącie 1xn, a poziome elementy w prostokącie 2xn odpowiadają elementom 1x2 w prostokącie 1xn. Tak więc nie ma między nimi żadnej różnicy.
Ponadto łamigłówka z prostokątem 1 x n jest dokładnie taka sama jak łamigłówka z krokami w „Fibonacci – 2”. Przechodzenie o jeden krok na raz to jak układanie kwadratu 1 na 1, a przechodzenie o dwa kroki na raz to jak układanie prostokąta 1 na 2. Obie łamigłówki są takie same, więc analiza i wyniki są takie same.
POSZUKIWANIE
Jeśli użyjemy prostokątów 1 na 1 i 1 na 3, wiele się zmieni. Spójrzmy na kilka pierwszych wartości i zastanówmy się, jak są obliczane. Otrzymujemy 1, 1, 2, 3, 4, 6 i 9 dla pierwszych kilku wartości. Generalnie, kolejna wartość jest sumą wartości bieżącej i wartości dwa kroki przed nią. Jest dość prosta do obliczenia, ale nie jest to już ciąg Fibonacciego.
Jeśli użyjemy 1 x 1, 1 x 2 i 1 x 3, sytuacja zmieni się jeszcze bardziej dramatycznie. Teraz pierwsze kilka wartości to 1, 2, 4, 7, 13 i 24. Następna wartość w sekwencji to suma trzech poprzednich wartości.
Ciągi takie, których kolejne wyrazy są definiowane za pomocą wzoru obejmującego wyrazy poprzednie, nazywane są ciągami rekurencyjnymi. Liczby Fibonacciego nie są jedynym ciągiem rekurencyjnym, ale prawdopodobnie najbardziej znanym.