Dláždění obdélníku
Úloha číslo: 3703
Kolika způsoby je možné vydláždit obdélník o rozměrech \(n \times k\) pomocí dlaždic \(1 \times 2\)?
Varianta
Řešte pro \(k=2\).
Nápověda
Označte počet dláždění jako \(a_n\) a najděte rekurentní vztah a vytvořující funkci, \(a_0\) vhodně dodefinujte.
Řešení
Dláždění obdélníku \(n \times 2\) lze získat buď z dláždění obdélníku délky \(n-1\) s tím, že poslední dlaždice je svisle, nebo z dláždění obdélníku délky \(n-2\) s tím, že poslední dvě dlaždice jsou položeny vodorovně.
Dostáváme \(a_n=a_{n-1}+a_{n-2}\), přičemž \(a_1=1\) a \(a_2=2\).
Odpověď
Počet dláždění obdélníku \(n\times 2\) je roven \(n\)-mu Fibonnaciho číslu \(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}2\right)^n-\left(\frac{1-\sqrt{5}}2\right)^n\right)\).
Varianta
A kolik různých způsobů dláždění stejnými dlaždicemi dostaneme pro \(k = 3\)?
Řešení
Podobně jako v předchozím případě se pokusíme dláždění obdélníku převést na předchozí případ. První pozorování je, že \(n\) je sudé.
Obdélník \(2\times 3\) lze vydláždit třemi způsoby. Pro \(k\ge 2\) platí, že obdélník \(2k \times 3\) lze vydláždit dvěma způsoby tak, že ho nelze rozložit na dva menší vydlážděné obdélníky výšky 3, viz obrázek.
Dostáváme rekurenci:
\(b_n=3b_{n-2}+2b_{n-4}+2b_{n-6}+…+2b_{0}\), přičemž dodefinujeme \(b_0=1\).
Odečteme-li od předchozí rekurence vyjádření:
\(b_{n-2}=3b_{n-4}+2b_{n-6}+…+2b_{0}\),
dostaneme \(b_n-4b_{n-2}+b_{n-4}=0\), což už lze vyřešit jako jiné rekurence.
Tento charakteristický mnohočlen má kořeny \(2\pm\sqrt3\).
Ze vztahů \(b_0=1\) a \(b_2=3\) dostaneme lineární kombinaci mocnin kořenů s koeficienty \(\frac12\pm\frac{\sqrt3}6\).
Odpověď
Počet dláždění obdélníku \(n \times 3\) je pro sudá \(n\) roven výrazu \(\left(\frac12+\frac{\sqrt3}6\right)\left(2+\sqrt3\right)^{\frac{n}2}+ \left(\frac12-\frac{\sqrt3}6\right)\left(2-\sqrt3\right)^{\frac{n}2}\).
Pro lichá \(n\) se takový obdélník vydláždit nedá.