Examkin

Soru

Zorluk: Çok zorAlt Küme

A={1,2,3,4,5,6,7}A = \{1, 2, 3, 4, 5, 6, 7\} kümesinin alt kümeleri arasından, içerisinde ardışık iki tam sayı bulunmayanlar bir SS sınıfı oluşturmaktadır.

Buna göre, SS sınıfına ait alt kümelerin kaç tanesinde en az bir asal sayı bulunur?

  1. A
    21
  2. B
    25
  3. 26Cevap
  4. D
    34
  5. E
    120

Cevap

İstenen şartları sağlayan 26 farklı alt küme vardır.
Soruda iki kısıtlama vardır: (1) Ardışık sayı içermeme, (2) En az bir asal sayı içerme.
Çözüm için 'Tüm Ardışık Olmayanlar' sayısından 'İçinde Asal Bulunmayan Ardışık Olmayanlar' sayısı çıkarılır.

1. Tüm Ardışık Olmayanlar: 7 elemanlı bir küme için bu sayı 34'tür (Fibonacci ilişkisi veya kombinasyon hesabı ile).
2. İstenmeyen Durum (Hiç Asal Yok): Kümedeki asal olmayanlar {1,4,6}\{1, 4, 6\}'dır. Bu sayıların hiçbiri ardışık olmadığı için, bu kümenin tüm alt kümeleri (8 adet) ardışık olmama kuralına uyar.
3. Sonuç: 34−8=2634 - 8 = 26.

Adım Adım Çözüm

1
Problemi iki aşamaya ayır: Önce ardışık sayı içermeyen tüm alt kümelerin sayısını bul, sonra bunlardan hiç asal sayı içermeyenleri çıkar.
Strateji: Tüm Durumlar - İstenmeyen Durumlar
'En az bir' ifadesi genellikle tümleyen mantığı ile (Tümü - Hiçbiri) daha kolay çözülür.
2
A={1,2,3,4,5,6,7}A = \{1, 2, 3, 4, 5, 6, 7\} kümesinde ardışık eleman içermeyen alt küme sayısını hesapla. Bu sayı Fn+2F_{n+2} Fibonacci sayısıdır veya eleman sayısına göre sayılabilir.
0 elemanlı: 1 (∅\emptyset)
1 elemanlı: 7
2 elemanlı: 15
3 elemanlı: 10
4 elemanlı: 1
Toplam: 1+7+15+10+1=341 + 7 + 15 + 10 + 1 = 34.
Ardışık eleman içermeyen alt küme sayısı hesabı.
3
İstenmeyen durumu belirle: İçinde ardışık sayı bulunmayan VE hiç asal sayı bulunmayan alt kümeler.
Asal olmayan elemanlar kümesi K={1,4,6}K = \{1, 4, 6\}.
AA kümesindeki asallar {2,3,5,7}\{2, 3, 5, 7\}, asal olmayanlar {1,4,6}\{1, 4, 6\}'dır.
4
K={1,4,6}K = \{1, 4, 6\} kümesinin alt kümelerinden ardışık eleman içermeyenleri say.
KK kümesinin hiçbir elemanı birbiriyle ardışık değildir (farkları 1 değildir). Bu nedenle KK'nın TÜM alt kümeleri şarta uyar. 23=82^3 = 8.
1, 4 ve 6 sayıları arasında ardışıklık ilişkisi yoktur, dolayısıyla ek bir elemeye gerek kalmaz.
5
Tüm geçerli durumlardan istenmeyen durumu çıkar.
34−8=2634 - 8 = 26.
Sonuç bulma.

Anahtar Kavram

Tümleyen Yöntemi ile Alt Küme Sayımı

İpuçları

1
'En az bir asal sayı bulunur' şartını doğrudan saymak yerine, tüm geçerli durumlardan hiç asal sayı bulunmayanları çıkarmayı deneyin.
2
Önce AA kümesinin, içinde ardışık sayı bulunmayan kaç alt kümesi olduğunu hesaplayın. (Bunu eleman sayılarına göre gruplayarak yapabilirsiniz: 0 elemanlı, 1 elemanlı, vb.)
3
Ardışık sayı içermeyen toplam alt küme sayısı 34'tür. Şimdi sadece asal olmayan {1,4,6}\{1, 4, 6\} elemanlarıyla oluşturulabilecek ardışık sayı içermeyen alt kümeleri bulup 34'ten çıkarın.

Daha Fazla Pratik

Benzer mantığı pekiştirmek için, ardışık sayı içermeyen alt kümelerin kaç tanesinde 'çift sayı bulunmaz' sorusu çözülebilir.

Alternatif Yöntem

Doğrudan Sayma Yöntemi: İçinde en az bir asal bulunan ardışık olmayan kümeleri; 1 asal içerenler, 2 asal içerenler vb. şeklinde gruplayarak da sayabilirsiniz, ancak bu yöntem çok daha fazla işlem gerektirir.
Tahmini Süre:4m 0s
Bu soruyu puanla

Konular

Alt Küme

Bu konudan daha fazla soru