31 Mayıs 2012 Perşembe

Re: [TMOZ:528723] Re: (UMO - 2012)

tşk ederim muharrem hocam matematikolimpiyat okulunda paylaşmıştım soruyu harika bir çözüm geldi, yolluyorum, orda da çok güzel insanlar var...

 

{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



31 Mayıs 2012 15:20 tarihinde Muharrem Şahin <muharrem49@gmail.com> yazdı:
Ö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.

111111000

Tü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: