1998 Antalya Matematik Olimpiyatı Lise 3 Soru 13

[matematikolimpiyati]

$K$ noktasından kalkan bir gezgin $m$ X $n$ tane noktadan oluşan matris üzerindeki noktalardan geçerek $L$ noktasına ulaşmak istemektedir. Gezi sırasında uygulanacak kurallar şunlardır:

(a) Bir satırdan yukardaki satıra geçerken istenilen nokta seçilebilir.
(b) Hareketler yukarı, sola ve sağa olabilir; geçilen bir noktadan bir daha geçmek ve aşağı dönmek yasaktır.

Buna göre, bu gezi kaç değişik biçimde yapılabilir?

$\textbf{a)}\ m!n!  \qquad\textbf{b)}\ m^{2n}  \qquad\textbf{c)}\ n^m  \qquad\textbf{d)}\ m^n  \qquad\textbf{e)}\ n^{2m}$

[Metin Can Aydemir]

Cevap: $\boxed{B}$

Her satırda, diğer satıra geçmeden önce yapılabilecek hamle sayısı $f(m)$ olsun, simetriden dolayı her satır için durum aynıdır. $n$ tane satır için bunu yapacağından cevabımız $(f(m))^n$ olacaktır. Şimdi sadece bir satıra göz atalım. Satırdaki noktaları $a_1,a_2,\dots,a_m$ ile adlandıralım. İlk sefer $a_i$'ye geçtiyse, ya direkt diğer satıra geçecek ya da belli bir miktar sağa veya sola gidecektir. Hem sağ hem sol yapamaz çünkü aynı noktadan geçmek zorunda kalır. Sağa $i-1$ defa gidebilirken, sola $m-i$ defa gidebilir. Hiçbir yere gitmemesi durumunu da eklersek, her taş için $$1+(i-1)+(m-i)=m$$ tane durum vardır. Yani $f(m)=m^2$ olmalıdır. Bu durumda da cevap $m^{2n}$ bulunur.