Examkin

Question

Difficulty: HardTekrarlı Permütasyon

Bir mikroçip üzerindeki iletim hatları yatay ve dikey yollardan oluşmaktadır. Elektrik akımı, sol alt köşedeki S(0,0)S(0,0) giriş kapısından başlayıp sadece sağa (pozitif xx yönünde) veya yukarı (pozitif yy yön��nde) hareket ederek sağ üst köşedeki E(5,4)E(5,4) çıkış kapısına ulaşacaktır. Mikroçipteki üretim hatasından dolayı C(2,2)C(2,2) ve D(3,3)D(3,3) koordinatlarındaki bağlantı noktalarından akım geçememektedir. Buna göre, akım giriş kapısından çıkış kapısına kaç farklı en kısa yoldan ulaşabilir?

  1. A
    6
  2. 42Answer
  3. C
    66
  4. D
    84
  5. E
    90

Answer

Doğru cevap 42'dir. Tüm yolların sayısından, geçilemeyen noktalardan geçen yolların sayısı çıkarılarak bulunur.
Doğru cevap 42'dir. S(0,0)S(0,0) noktasından başlayıp sadece sağa ve yukarı hareket ederek E(5,4)E(5,4) noktasına ulaşan tüm yolların sayısı 126126 olarak bulunur. Yasaklı olan C(2,2)C(2,2) noktasından geçen yolların sayısı 6060, D(3,3)D(3,3) noktasından geçen yolların sayısı da 6060 adettir. Hem C(2,2)C(2,2) hem de D(3,3)D(3,3) noktalarından sırasıyla geçen yolların sayısı 3636'dır. Küme birleşim formülü (içerme-dışarma ilkesi) gereği, engelli noktalardan en az birinden geçen toplam yol sayısı 60+60−36=8460 + 60 - 36 = 84 olur. Bu durumda geriye kalan geçerli yolların sayısı 126−84=42126 - 84 = 42 olarak bulunur.

Step-by-Step Solution

1
S(0,0)S(0,0) noktasından E(5,4)E(5,4) noktasına olan tüm en kısa yolların sayısını tekrarlı permütasyon ile hesaplayın.
(5+4)!5!×4!=9!5!×4!=126 \frac{(5+4)!}{5! \times 4!} = \frac{9!}{5! \times 4!} = 126
Herhangi bir kısıtlama olmadan gidilebilecek tüm yolların toplam sayısını belirlemek için.
2
C(2,2)C(2,2) noktasından geçen en kısa yolların sayısını hesaplay��n.
S(0,0)→C(2,2)S(0,0) \rightarrow C(2,2) için 22 sağ, 22 yukarı ⇒4!2!×2!=6\Rightarrow \frac{4!}{2! \times 2!} = 6 yol. C(2,2)→E(5,4)C(2,2) \rightarrow E(5,4) için 33 sağ, 22 yukarı ⇒5!3!×2!=10\Rightarrow \frac{5!}{3! \times 2!} = 10 yol. Toplam: 6×10=606 \times 10 = 60 yol.
İlk arızalı noktaya uğrayan tüm geçersiz yolların sayısını belirlemek için.
3
D(3,3)D(3,3) noktasından geçen en kısa yolların sayısını hesaplayın.
S(0,0)→D(3,3)S(0,0) \rightarrow D(3,3) için 33 sağ, 33 yukarı ⇒6!3!×3!=20\Rightarrow \frac{6!}{3! \times 3!} = 20 yol. D(3,3)→E(5,4)D(3,3) \rightarrow E(5,4) için 22 sağ, 11 yukarı ⇒3!2!×1!=3\Rightarrow \frac{3!}{2! \times 1!} = 3 yol. Toplam: 20×3=6020 \times 3 = 60 yol.
İkinci arızalı noktaya uğrayan tüm geçersiz yolların sayısını belirlemek için.
4
Hem C(2,2)C(2,2) hem de D(3,3)D(3,3) noktasından geçen en kısa yolların sayısını hesaplayın.
S(0,0)→C(2,2)S(0,0) \rightarrow C(2,2) için 66 yol. C(2,2)→D(3,3)C(2,2) \rightarrow D(3,3) için 11 sağ, 11 yukarı ⇒2!1!×1!=2\Rightarrow \frac{2!}{1! \times 1!} = 2 yol. D(3,3)→E(5,4)D(3,3) \rightarrow E(5,4) için 33 yol. Toplam: 6×2×3=366 \times 2 \times 3 = 36 yol.
Her iki engelli noktaya da sırasıyla uğrayan ortak yolların sayısını belirlemek için. Bu yollar hem adım 2'de hem de adım 3'te iki kez sayılmıştır.
5
İçerme-Dışarma İlkesi kullanarak en az bir engelli noktadan geçen toplam yol sayısını bulun.
60+60−36=8460 + 60 - 36 = 84 yol.
Kesişim kümesindeki ortak yolların mükerrer sayılmasını engellemek amacıyla.
6
Toplam yol sayısından engelli noktalardan geçen yolların sayısını çıkararak geçerli yolların sayısını bulun.
126−84=42126 - 84 = 42 yol.
Hiçbir engelli noktaya uğramayan geçerli iletim hatlarının sayısını bulmak için.

Key Concept

Tekrarlı permütasyon formülü ve İçerme-Dışarma İlkesi (Kümelerde Birleşim Formülü) kullanılarak kısıtlı ızgara yollarının hesaplanması.

Alternative Method

Nokta toplama yöntemi (veya köşegen toplama yöntemi) kullanılarak da sonuca ulaşılabilir. S(0,0)S(0,0) noktasından başlanarak her bir kesişim noktasındaki yolların sayısı, o noktanın solundaki ve altındaki noktaların yol sayılarının toplamı olarak yazılır. Bu işlem sırasında C(2,2)C(2,2) ve D(3,3)D(3,3) noktalarının üzerindeki yol sayıları arızalı oldukları için 00 kabul edilir ve toplama işlemine bu şekilde devam edilerek E(5,4)E(5,4) noktasına ulaşıldığında 4242 değeri elde edilir.
Estimated Time:2m 30s
Rate this question

Topics

Tekrarlı Permütasyon

More questions from this topic