2006 Antalya Matematik Olimpiyatı Soru 17

[matematikolimpiyati]

$A$ karesinde bulunan bir karınca$,$ şekildeki gibi$,$



sadece üç yönde hareket edebilmektedir. Taralı karelerden geçmemek koşuluyla$,$ karınca $B$ karesine kaç farklı yoldan ulaşabilir?

$\textbf{a)}\ 80  \qquad\textbf{b)}\ 24  \qquad\textbf{c)}\ 64  \qquad\textbf{d)}\ 16  \qquad\textbf{e)}\ 40$

[Metin Can Aydemir]

Cevap: $\boxed{A}$

$2\times 2$'lik bir kısımda alt, sağ ve soldaki karelere $x,y,z$ farklı şekilde gidilebiliyorsa üstteki kareye $x+y+z$ farklı şekilde gidilebilir çünkü üst kareye sadece bu üç kareden gidilebilir. $A$'nın olduğu kareye $1$ farklı şekilde gidilmesiyle başlarsak, yasaklı karelere $0$ yazarak tüm kareleri doldurabiliriz. Bu şekilde yazarsak, $B$ karesine $80$ farklı şekilde gidilebilir.