Examkin

Soru

Zorluk: Çok zorTekrarlı Permütasyon

Analitik düzlemde A(0,0)A(0,0) noktasında bulunan bir hareketli, yalnızca 1 birim sağa veya 1 birim yukarı doğru hareket ederek en kısa yoldan B(4,4)B(4,4) noktasına ulaşmak istemektedir. Bu hareketli, yolculuğu boyunca üst üste en fazla iki kez aynı yönde adım atabilmektedir (yani güzergâhında yan yana 3 tane sağa veya 3 tane yukarı adımı bulunmamaktadır). Buna göre, bu hareketlinin AA noktasından BB noktasına gidebileceği kaç farklı yol vardır?

Cevap: 34

Cevap

İstenen koşullara uygun yolların toplam sayısı 34'tür.
Doğru cevap, kısıtlamasız tüm yolların sayısından (70), en az 3 ardışık sağa adımı veya en az 3 ardışık yukarı adımı içeren istenmeyen yolların sayısının (36) kapsama-dışlama ilkesiyle çıkarılması sonucu 34 olarak bulunur.

Adım Adım Çözüm

1
Toplam atılması gereken sağa (S) ve yukarı (Y) adım sayılarını belirleyip tüm olası yolların sayısını hesaplamak.
Toplam 8 adım (4 sağa, 4 yukarı) atılmalıdır. Kısıtlamasız yolların sayısı: 8!4!⋅4!=70\frac{8!}{4! \cdot 4!} = 70 olur.
Referans alınacak kısıtlamasız durum sayısını tekrarlı permütasyonla bulmak için.
2
Koşulları sağlamayan (istenmeyen) durumları tanımlamak ve küme sembollerini belirlemek.
En az bir tane 'SSS' içeren yolların kümesi AA, en az bir tane 'YYY' içeren yolların kümesi BB olsun. İstenen durum sayısı: 70−∣A∪B∣=70−(∣A∣+∣B∣−∣A∩B∣)70 - |A \cup B| = 70 - (|A| + |B| - |A \cap B|) formül��yle modellenir.
Kural ihlallerini kapsama-dışlama ilkesiyle matematiksel olarak ifade etmek için.
3
Yalnızca S adımlarının kuralı ihlal ettiği durumların sayısı olan ∣A∣|A| değerini hesaplamak.
1) Tek blok 'SSSS' için 5!1!⋅4!=5\frac{5!}{1! \cdot 4!} = 5 durum; 2) İki ayrı blok 'SSS' ve 'S' için (52)⋅2!=20\binom{5}{2} \cdot 2! = 20 durum vardır. Toplamda ∣A∣=25|A| = 25 olur. Simetriden dolayı ∣B∣=25|B| = 25 elde edilir.
Harfleri gruplandırarak istenmeyen durumların her birinin ayrı ayrı eleman sayılarını bulmak için.
4
Hem S hem de Y adımlarının kuralı ihlal ettiği ortak durumların sayısı olan ∣A∩B∣|A \cap B| kesişim kümesini hesaplamak.
Farklı blok tiplerinin alternatif dizilimleri analiz edilerek: 2 (Durum 1)+2 (Durum 2)+2 (Durum 3)+8 (Durum 4)=142 \text{ (Durum 1)} + 2 \text{ (Durum 2)} + 2 \text{ (Durum 3)} + 8 \text{ (Durum 4)} = 14 durum bulunur.
Kapsama-dışlama formülünde iki kez çıkarılan durumları geri eklemek amacıyla kesişim kümesini bulmak için.
5
Kapsama-dışlama formülünü uygulayarak nihai doğru cevaba ulaşmak.
∣A∪B∣=25+25−14=36|A \cup B| = 25 + 25 - 14 = 36 ve İstenen Yol Sayısı = 70−36=3470 - 36 = 34 olarak bulunur.
Tüm durumlardan istenmeyen durumların birleşimini çıkartıp sonucu bulmak için.

Anahtar Kavram

Tekrarlı Permütasyon ve Kapsama-Dışlama İlkesi
Bu soruyu puanla

Konular

Tekrarlı Permütasyon

Bu konudan daha fazla soru