Crossing Roads 3

Treating the problem as getting from $(2,100)$ to $(0,0)$ makes the notation easier, also we can ignore the 1 minute movement time on each edge for now, and add 102 on at the end:

Let $E(a,b)$ be the expected time taken to get from $(a,b)$ to $(0,0)$ .

$E(0,n) = E(n,0) = \frac{n}{2}$ .

For $a \leq b, E(a,b) = \frac{1}{4}E(a-1,b) + \frac{3}{4}E(a,b-1) + \frac{1}{4}$ .

---

Let $S_n = E(1,n) = \frac{1}{4}E(0,n) + \frac{3}{4}S_{n-1} + \frac{1}{4} = \frac{n}{8} + \frac{1}{4} + \frac{3}{4}S_{n-1}$ .

$S_0 = \frac{1}{2}$ , so:

$S_n = \frac{1}{8}\sum_{i=0}^{n-1} (\frac{3}{4})^i (n-i) + \frac{1}{4}\sum_{i=0}^{n-1} (\frac{3}{4})^i + \frac{1}{2} (\frac{3}{4})^n$

$= \frac{1}{2}(n - 3(1-(\frac{3}{4})^n)) + (1 - (\frac{3}{4})^n) + \frac{1}{2}(\frac{3}{4})^n = \frac{n}{2} - \frac{1}{2} + (\frac{3}{4})^n$ .

---

For $n > 0$ let $F_n = E(2,n) = \frac{1}{4}S_n + \frac{3}{4}F_{n-1} + \frac{1}{4} = (\frac{n}{8} - \frac{1}{8} + \frac{1}{4}(\frac{3}{4})^n) + \frac{1}{4} + \frac{3}{4}F_{n-1}$ ,

where $F_0 = \frac{5}{6}$ , so $F_1 = E(2,n) = \frac{17}{16}$ .

$F_n = \frac{n}{8} + \frac{1}{8} + \frac{1}{4}(\frac{3}{4})^n + \frac{3}{4} F_{n-1}$

$F_n = [ \frac{1}{2}(n - 3(1-(\frac{3}{4})^n)) ] + [ \frac{1}{2} (1 - (\frac{3}{4})^n) ] + [ \frac{n}{4}(\frac{3}{4})^n ] + [ \frac{5}{6}(\frac{3}{4})^n ]$

$= \frac{n}{2} - 1 + (\frac{11}{6} + \frac{n}{4} ) (\frac{3}{4})^n$ .

---

Hence,

$E(2,100) = F_{100} = 49 + (\frac{11}{6} + 25 ) (\frac{3}{4})^{100} = 49 + \frac{161 * 3^{100}}{6 * 4^{100}} = 49 + \frac{3^{99} \times 7 \times 23}{2^{201}}$ .

For our problem, the expected time is $151 + 2^{-201} \times 3^{99} \times 7^1 \times 23^1$ .

So our desired sum is $151 + (2 + 3 + 7 + 23) + (201 + 99 + 1 + 1) = 151 + 35 + 302 = 488$ .