2009 Antalya Matematik Olimpiyatı Soru 04

[matematikolimpiyati]

Şekilde$,\ 6$ satır ve $4$ sütunu olan tablonun sol alt köşesinden $(A$ noktasından$)$ sağ üst köşesine $(D$ noktasına$),$ çizgiler üzerinde sağa veya yukarıya hareket edilerek gidilecektir. $B$ ve $C$ noktalarının en az birinden geçmek koşuluyla$,$ kaç farklı yol izlenebilir?

$\textbf{a)}\ 118  \qquad\textbf{b)}\ 124  \qquad\textbf{c)}\ 122  \qquad\textbf{d)}\ 130  \qquad\textbf{e)}\ 132$

[Metin Can Aydemir]

Cevap: $\boxed{C}$

$A(0,0)$, $B(2,2)$, $C(3,3)$ ve $D(4,6)$ noktaları verilmiştir. $(a,b)$ noktasından $(a+x,b+y)$ noktasına sadece sağa ve yukarı hareket edilerek gidilmesi ile $x$ tane sağa ($S$) ve $y$ tane yukarı ($Y$) hareketinin sıralanmasıdır. Tekrarlı permütasyondan $\frac{(x+y)!}{x!y!}=\dbinom{x+y}{x}$ farklı şekilde gidilebileceği görülebilir.

$B$'den geçilen yolların sayısı $\dbinom{2+2}{2}\dbinom{2+4}{2}=90$'dır.
$C$'den geçilen yolların sayısı $\dbinom{3+3}{3}\dbinom{1+3}{1}=80$'dir.
Hem $B$'den, hem de $C$'den geçilen yolların sayısı $\dbinom{2+2}{2}\dbinom{1+1}{1}\dbinom{1+3}{1}=48$'dir. İçerme-dışarma prensibinden, $B$ veya $C$'den geçilen yolların sayısı $$90+80-48=122$$ bulunur.