Tübitak Lise 1. Aşama 2007 Soru 20

[ERhan ERdoğan]

$9$ ardışık bölümden oluşan bir şeridin her bölümü kırmızı veya beyaza boyanıyor. Herhangi bitişik iki bölüm birlikte beyaza boyanamıyorsa, bu boyama kaç değişik biçimde yapılabilir?

$
\textbf{a)}\ 34
\qquad\textbf{b)}\ 89
\qquad\textbf{c)}\ 128
\qquad\textbf{d)}\ 144
\qquad\textbf{e)}\ 360
$

[Lokman Gökçe]

Yanıt: $\boxed{B}$

Problemi genel halde $n$ ardışık bölme için indirgemeli dizi yöntemiyle çözelim. Herhangi bitişik iki bölümün beyaza boyanmadığı durumların sayısı $a_n$ olsun. Kolayca görüleceği üzere $a_1=2$, $a_2=3$ tür. Biz $a_9$ değerini bulmalıyız. $n$ ardışık bölmenin $n$ inci hanesi için iki boyama seçeneği olduğundan tüm durumların sayısını iki alt durumun toplamı olarak ifade edeceğiz.

$n$ inci hane kırmızı ise, $n-1$ inci hane ve daha öncesini $a_{n-1}$ yolla boyayabiliriz.

$n$ inci hane beyaz ise, $n-1$ inci hane mutlaka kırmızıdır. $n-2$ inci hane ve daha öncesini $a_{n-2}$ yolla boyayabiliriz.

Böylece toplamda $a_n = a_{n-1}+a_{n-2}$ şeklinde bulunur. Fibonacci dizisinin indirgeme bağıntısını elde ettiğimize dikkat edilebilir. $a_1=2$, $a_2=3$ olduğunu kullanarak $(a_n)=(2,3,5,8,13,21,34,55,89, \dots)$ yazabiliriz. $a_9=89$ bulunur.