Tübitak Ortaokul 1. Aşama 2012 Soru 02

[Egemen]

$\{1, 2\ldots ,17\}$ kümesinin farkları $4$ olan herhangi iki eleman içermeyen kaç alt kümesi vardır?

$\textbf{a)}\ 3490\qquad \textbf{b)}\ 6480\qquad \textbf{c)}\ 6656\qquad \textbf{d)}\ 6966\qquad \textbf{e)}\ 8264\qquad$

[Eray]

Yanıt: $\boxed{C}$

$\{1,2,\cdots,17\}=\{1,5,9,13,17\}\cup\{2,6,10,14\}\cup\{3,7,11,15\}\cup\{4,8,12,16\}$
Her kümenin, yan yana $2$ eleman bulunmayacak şekilde kaç altkümesi olduğunu bulmalıyız.

Lemma: $\{1,2,\cdots, n\}$ kümesinin elemanlarından, ardışık iki sayı içermeyecek şekilde $f_{n+2}$ tane alt kümesi vardır. Burada $(f_n)=(1,1,2,3,5,8,13,21,34,55, \dots )$ şeklindeki Fibonacci dizisidir.

İspatı indirgemeli diziler kullanılarak kolaylıkla yapılabilir.

O halde ilk kümenin istenen şartları sağlayan $13$, diğer üç kümenin $8$ altkümesi vardır. Aradığımız sayı ise $13\cdot8\cdot8\cdot8=6656$'dır.