Şekilde çizgilerin üzerinden gitmek koşuluyla, $A$ dan başlayıp beş noktadan geçtikten sonra $C$ ye varan (örneğin $ABCBADC$ gibi) kaç farklı yol vardır?
Başlık: Ynt: Tübitak Lise 1. Aşama 1993 Soru 30
Gönderen: Lokman Gökçe - Eylül 02, 2022, 03:21:26 ös
Yanıt: $\boxed{E}$
(Lokman GÖKÇE)
Elbette, adım sayısı kısmen az olduğu için alt durumlara ayırıp sayarak sonuca gitmek mümkündür. Halen alt durum hesaplamasının bir parça zorluğu vardır. Fakat, adım sayısı daha fazla oldukça alt durum inceleme hesaplamaları da daha fazla artacaktır. Çözümün kafa karıştırıcılığı da artacaktır. Bu sebeple, probleme genel bir çözüm yolu bulmayı deneyelim. Bu yolda, ısrarla bir $a(n)$ dizisi için doğrusal indirgeme bağıntısı elde etmeye odaklandığım için inatçı yol olarak isimlendireceğim.
$X$ noktasından harekete başlayıp $n$ hamle sonunda $C$ noktasına ulaşılan yolların sayısı $x(n)$ olsun. $X \in \{A, B, C, D\}$ için sırasıyla $x\in \{a, b, c, d\}$ gösterimlerini kullanalım. $a(1)=1, a(2)=2$, $b(1)=d(1)=1$, $b(2)=d(2)=1$, $c(1)=0, c(2)=3$ hesaplamalarını yapmak kolaydır. Ayrıca simetriden dolayı $b(n)=d(n)$ dir.
$A$ dan harekete başladığımızda ilk hamlemizde ya $B$ ye, ya $C$ ye ya da $D$ ye gidebiliriz. $b(n-1)=d(n-1)$ olduğundan $$a(n) = 2b(n-1) + c(n-1) \tag{1}$$ $B$ dan harekete başladığımızda ilk hamlemizde ya $A$ ya ya da $C$ ye gidebiliriz. $$b(n) = a(n-1) + c(n-1) \tag{2}$$ $C$ dan harekete başladığımızda ilk hamlemizde ya $B$ ye, ya $A$ ya ya da $D$ ye gidebiliriz. $b(n-1)=d(n-1)$ olduğundan $$c(n) = 2b(n-1) + a(n-1) \tag{3}$$ bağıntıları yazılır.
$(1)$ ve $(3)$ ün farkından, $a(n)-c(n) = (c-1)-a(n-1)$ olup $$a(n)+a(n-1)=c(n)+c(n-1) = m(n) \tag{4}$$
elde edilir. $(2)$ de $n$ yerine $n+1$ koyup $(2)$ eşitliği ile yeniden toplarsak $$b(n) + b(n+1) = a(n)+a(n-1)+c(n)+c(n-1) = 2m(n) \tag{5}$$ elde edilir. $(1)$ ve $(3)$ ün toplamından, $a(n) + c(n) = a(n-1) + c(n-1) + 4b(n-1)$ olur. Bu bağıntıda $n$ yerine $n+1$ yazıp bu bağıntı ile yeniden toplarsak $$m(n+1) = m(n) + 4m(n-1) \tag{6}$$ eşitliği elde edilir. $(4)$ deki $m(n) = a(n) + a(n-1)$ bağıntısını $(6)$ da kullanırsak $$a(n+1) = 5a(n-1) + 4a(n-2) \tag{7}$$ $n\geq 3$ tam sayıları için kullanabileceğimiz doğrusal indirgeme bağıntısına ulaşırız. $(1)$ yardımıyla $a(3) = 2b(2) + c(2) = 2 + 3 = 5$ bulunur.
Daha İnatçılar İçin Not: $a(n+1) = 5a(n-1) + 4a(n-2) $ bağıntısının karakteristik denklemi $r^3 - 5r - 4 = 0$ dır. $r_1=-1$ bir kök olduğundan $(r+1)(r^2 - r - 4)=0$ biçiminde yazılır. Diğer kökler ise $r_{2,3}=\dfrac{1 \mp \sqrt{17}}{2}$ olur. $A_1, A_2, A_3$ gerçel sabitler olmak üzere $(a_n)$ dizisinin genel terimi $$ a(n) = A_1r_1^n + A_2r_2^n + A_3r_3^n \tag{8}$$ formundadır. $a(1)=1, a(2)=2, a(3)=5$ değerlerini kullanarak $A_1,A_2,A_3$ katsayılarını çözebiliriz. Bu noktada Wolframalpha'dan yardım alarak veya kaba kuvvet işlemlere girişerek