{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} kümesinin dört tane ardışık tam sayı içermeyen kaç alt kümesi vardır?
a) 596 b) 648 c) 679 d) 773 e) 812
Çözüm:
Problemi n elemanlı bir küme için çözelim. A = {1, 2, 3, … , n} olsun. A kümesinden ardışık dört tane tamsayı içermeyen bir S alt kümesi aldığımızı düşünelim. An, n elemanlı bir kümenin ardışık dört tane tamsayı içermeyen alt kümelerinin sayısı olsun. Alabileceğimiz alt kümeleri dört guruba ayırabiliriz.
1.Gurup: Eğer n ,n-1 ve n-2, S alt kümesinin elemanları ise S alt kümesi verilen şart gereği n - 3 elemanını içermez. Böylelikle yazabileceğimiz alt kümelerin sayısı An-4 tür. Yani n – 4 tane elemanı olan kümenin dört tane ardışık sayı içermeyen alt küme sayısı kadardır.
2.Gurup: Eğer n ve n-1 elemanları S alt kümesinin elemanı fakat n – 2 elemanı değil ise, ardışık dört tamsayı içermeyen An – 3 tane alt küme tanımlayabiliriz.
3.Gurup: Eğer n elemanı S alt kümesinin elemanı fakat n – 1 elemanı S alt kümesinin elemanı değil ise bulabileceğimiz alt küme sayısı An-2 olacaktır. (kullanabileceğimiz n-2 eleman kaldığı için)
4.Gurup: Son olarak, eğer dört tane ardışık tamsayı içermeyen S alt kümesi n elemanını içermiyor ise yazabileceğimiz alt kümelerin sayısı An – 1 olarak bulunur.
Yazabileceğimiz bütün alt kümeler bu dört guruptan mutlaka birinin içerisindedir ve bir alt küme birden fazla gurubun içerisinde yer alamaz.
Böylelikle n elemanlı bir küme için ardışık dört tane tamsayı içermeyen alt kümelerin sayısı
An = An – 1 + An – 2 + An – 3 + An – 4
indirgemeli dizisi olarak belirlenir ve başlangıç değerlerinin
A0 = 1, (sadece Æ şartı sağlar.)
A1 = 2, (Æ ve {1} şartı sağlar.)
A2 = 4, (Æ,{1},{2} ve{1,2} kümeleri verilen şartı sağlar.)
A3 = 8, (3 elemanlı kümenin tüm alt kümeleri verilen şartı sağlayacaktır.)
olduğu görülür
Soruda A10 değeri isteniyor.
Bu indirgemeli dizinin terimleri, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773 olarak gider.
Sonuç olarak soruda istenen A10 = 773 olarak hesaplanır.
Not: Bu problemin çözümündeki fikir, n elemanlı kümenin ardışık k tane tamsayı içermeyen alt kümelerinin sayısının bulunması için de uygulanabilir.
Çözüm: Ali İlker Bağrıaçık
Örnek{1,2,3,4,5,6,7,8,9} kümesinin,en az 5 elemanının sıralı olduğu 6 elemanlıalt kümelerinin sayısını bulalım.111111000Tümü sıralı, 6 elemanlı alt kümelerin sayısı = C(4,1) (123456, 234567, 345678, 456789)1000 sıralamalarının sayısı = C(1+3, 3) = 4!/(1!.3!)En az 5'i sıralı 6 elemanlı alt kümelerin sayısı = C(4,1).C(4,3) = 16--
Yanlış anlaşılmalara ve polemik oluşturacak durumlara meydan verecek mesajlardan kaçınalım lütfen...
EKLEDİĞİNİZ RESİMLERİN BOYUTLARINA LÜTFEN DİKKAT EDİNİZ!!!...
YOLLADIĞINIZ MESAJLARA LÜTFEN KONU BAŞLIĞI YAZINIZ!!!...
http://www.facebook.com/pages/Matematik-Geometri/150709609688?ref=mf
--
Kemal Hasoğlu Lisesi
Bahçelievler İstanbul
HAYDAR DOOOST
--
Yanlış anlaşılmalara ve polemik oluşturacak durumlara meydan verecek mesajlardan kaçınalım lütfen...
EKLEDİĞİNİZ RESİMLERİN BOYUTLARINA LÜTFEN DİKKAT EDİNİZ!!!...
YOLLADIĞINIZ MESAJLARA LÜTFEN KONU BAŞLIĞI YAZINIZ!!!...
http://www.facebook.com/pages/Matematik-Geometri/150709609688?ref=mf
Hiç yorum yok:
Yorum Gönder