Crossing Roads 2

Working backwards calculating the expected amount of time taken from each point, we get this: (All numbers present are numerators over $65536$ and ignore the $1$ minute of walking between vertices).

$\begin{matrix} 163840&&131072&&98304&&65536&&32768&&0\\ 146624&&119040&&93184&&69632&&49152&&-\\ 146256&&124288&&104192&&86016&&-&&-\\ 156364&&137888&&120576&&-&&-&&-\\ 171179&&154272&&-&&-&&-&&-\\ 187563&&-&&-&&-&&-&&-\\ \end{matrix}$

Each value is calculated as (Time when move up) $/4 + 3*$ (Time when move right) $/4 + 16384$ , where $\frac{16384}{65536} = \frac{1}{4}$ .

The top row is $32768 +$ (Time when move right). And the middle diagonal is simplified to (Time when move up) $+ 16384$ .

The rest of the squares are reflections from symmetry.

---

The answer is $10 + \frac{187563}{65536}$ .

$m+n = 187563 + 65536 = 253099$ .

To simplify the computations, I reversed the direction of the path, so I'm at $(5,5)$ going towards $(0,0)$ I created a matrix of expected walking times towards $(0,0)$

Note $P[0,0] = 0$ .

Along horizontal and vertical boundaries of the grid, I assumed the optimal strategy would be to head straight towards $(0,0)$ . (This is easily verified.) Thus $P[j,0] = P[0,j] = (3/2)+P[j+1,0]$ for $1 \leq j \leq 6.$

When at a boundary, one can move directly immediately with probability $1/2$ , and must wait an extra minute with probability 1/2. Hence the " $3/2$ ".

For $1 \leq i,j \leq 5$ , we use a strategy of trying to head towards the diagonal immediately, whenever possible. If not, then one should move immediately, if possible. If both paths are red, then one waits a turn and heads toward the diagonal.

This yields a recursive relationship $P [i,j] = 0.5 (1 + \min (P[i-1,j],P[i,j-1]) + 0.25 (1 + \max (P[i-1,j],P[i,j-1])) + 0.25 (2 + \min (P[i-1,j],P[i,j-1]))$

In decimal form, the matrix P is

$\begin{array}{c}P = & & & & & & \\ & 0.00000000 & 1.50000000 & 3.00000000 & 4.50000000 & 6.00000000 & 7.50000000 \\ & 1.50000000 & 2.75000000 & 4.06250000 & 5.42187500 & 6.81640625 & 8.23730469 \\ & 3.00000000 & 4.06250000 & 5.31250000 & 6.58984375 & 7.89648438 & 9.23168945 \\ & 4.50000000 & 5.42187500 & 6.58984375 & 7.83984375 & 9.10400391 & 10.38592529 \\ & 6.00000000 & 6.81640625 & 7.89648438 & 9.10400391 & 10.35400391 & 11.61198425 \\ & 7.50000000 & 8.23730469 & 9.23168945 & 10.38592529 & 11.61198425 & 12.86198425 \\ \end{array}$

To get the final answer, convert P[5,5] - 10 to a fraction. I used the Python Fraction package:

Fraction(P[5,5]-10)

outputs

Fraction(187563, 65536)

And $187563 + 65536 = 253099.$

As has already noted, the only way to approach this is iteratively from point (5,5). Ignoring the travelling time also helps simplify matters because we are interested only in working out how much time is "wasted".

The reason for using backwards iteration is that there is a choice involved at each junction if both North and East routes are available. For an optimal route we would choose the route that moves us to the point with lowest remaining expected "waste" - call it E(x,y). So calculating E(x,y) requires knowledge of E(x+1,y) and E(x,y+1).

Beyond that it is a fairly laborious exercise without a computer.