2 x 30 Tahta {Çözüldü}

[senior]

2 x 30 bir tahtayı, 1 x 2, 2 x 1 ve 2 x 2 bloklar kullanılarak kaç farklı şekilde oluşturabiliriz? (Tahtayı döndürmeyin)

[Lokman Gökçe]

$2 \times 30$ tahtayı $a_n$ yolla kapladığımızı düşünelim. Tahtanın sonu şu üç biçimde kaplanmış olabilir. Bir tane $2\times 1$ blok dik durumlu gelmiş olabilir, iki tane $2\times 1$ blok üst üste gelerek $2\times 2$ ebadında bir kareyi kaplamış olabilir, bir tane $2\times 2$ kullanılmış olabilir. Bu durumların sayısı sırasıyla $a_{n-1}$, $a_{n-2}$ ve $a_{n-2}$ dir. Dolayısıyla

$ a_n = a_{n-1} + 2a_{n-2} $    ... (1)

dir.  (1) indirgemeli dizisinin karakteristik polinomu $r^2 - r - 2 =0$ olup kökler $r_1= -1$, $r_2 = 2$ dir. Genel terim $a_n = A(-1)^n + B2^n$ biçimindedir. $a_1 = 1$, $a_2 =3$ olduğunu hesaplamak kolaydır. Bu değerler yardımıyla $A=\dfrac{1}{3}$, $B=\dfrac{2}{3}$ bulunur. O halde

$ a_n = \dfrac{(-1)^n +2^{n+1}}{3} $    ... (2)

elde edilir. $n=30$ için $a_{30}= \dfrac{ 2^{31}+1}{3}=715827883$ sonucuna ulaşılır.