Zbiór zadań, (zadania różne)
Zadanie 189
Na ile sposobów prostokąt o wymiarach 10 na 2 można pokryć nierozróżnialnymi prostokątnymi kostkami o wymiarach 2 × 1 tak, aby kostki nie zachodziły na siebie?
Rozwiązanie
Niech an będzie liczbą różnych pokryć nierozróżnialnymi prostokątnymi kostkami o wymiarach 2 na 1.
Rozpatrzmy prostokąty o długości n i szerokości 2:
dla n = 1, a1 = 1
dla n = 2, a2 = 2
dla n = 3, a3 = 3
dla n = 4, a4 = 5
dla n = 5, a5 = 8
Pokrycie prostokąta o wymiarach n × 2 powstaje z pokrycia prostokąta o wymiarach (n - 1) × 2 przez dołączenie prostokąta o wymiarach 2 × 1 ustawionego pionowo lub pokrycia prostokąta o wymiarach (n - 2) × 2 przez dołączenie dwóch prostokątów ułożonych poziomo. Każde z tych pokryć są różne.
Ogólnie dla n > 2 zachodzi an = an - 1 + an - 2.
Rozpoznajemy w tym łatwo ciąg Fibonacciego.
Dla prostokąta 10 × 2, a10 = 89
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>