Geomania.Org Forumları
Yarışma Soruları => Tübitak Ortaokul 2. Aşama => 2003 => Konuyu başlatan: ERhan ERdoğan - Temmuz 15, 2016, 05:44:06 ös
-
$\left \{1,2,3,4,5,6,7,8,9,10,11 \right \}$ kümesinin, herhangi iki ardışık tam sayı içermeyen kaç alt kümesi vardır?
-
İndirgemeli diziler yardımıyla çözülebilir.
$\{1,2,3,\dots,n\}$ kümesinin herhangi ardışık iki tam sayı içermeyen alt küme sayısına $a_n$ diyelim. Bu küme içerisinden bu şekilde seçeceğimiz alt küme $A$ olsun. Durum incelemesi yapalım.
$(i)$ $n\in A$ ise ardışık tam sayı bulunmayacağından $n-1\not\in A$ olmalıdır. Elimizde kalan küme $\{1,2,3,...,n-2\}$ olur. Bu kümeden istenen şekilde $a_{n-2}$ farklı alt küme seçilebilir.
$(ii)$ $n\not\in A$ ise elimizde kalan küme $\{1,2,3,...,n-1\}$ olur. Bu kümeden istenen şekilde $a_{n-1}$ farklı alt küme seçilebilir.
$(i)$ ve $(ii)$ durumları tüm durumları kapsar. O halde işlemlerimiz gereği $a_n=a_{n-1}+a_{n-2}$ olmalıdır. Bu dizinin ilk iki terimini bulursak kalan terimlerine de rahatlıkla ulaşabiliriz.
$n=1$ durumu için $\{1\}$ kümesinden boş küme ve tek elemanlı küme olmak üzere 2 küme seçilebilir. $a_1=2$ olmalıdır.
$n=2$ durumu için $\{1,2\}$ kümesinden boş küme ve tek elemanlı kümeler seçilebilir. $a_2=3$ olmalıdır.
Bu başlangıç terimleri yardımıyla $a_{11}$'i hesaplarsak cevabın $233$ olduğunu görürüz.
not: Fibonacci dizisini $(f_n)=(1,1,2,3,5,8,13,21,...)$ olarak tanımlarsak $a_n=f_{n+2}$ olduğunu görürüz. Yani özünde sorunun cevabı genel olarak $f_{n+2}$'dir.