Geomania.Org Forumları

Yarışma Soruları => Tübitak Ortaokul 1. Aşama => 2012 => Konuyu başlatan: Egemen - Haziran 06, 2014, 05:38:48 ös

Başlık: Tübitak Ortaokul 1. Aşama 2012 Soru 02
Gönderen: Egemen - Haziran 06, 2014, 05:38:48 ös

$\{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$

Başlık: Ynt: Tübitak Ortaokul 1. Aşama 2012 Soru 02
Gönderen: Eray - Haziran 06, 2014, 07:27:02 ös

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.

Alıntı yapılan: scarface - Mayıs 31, 2014, 03:00:25 ös

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.