Vole Crossing

Relevant wiki: Linear Recurrence Relations - Problem Solving

To calculate the probability that a random path is successful, we can count the number of successful paths and divide by the total number of paths.

We can represent any path as a word consisting of $W$ s and $E$ s, where $W$ represents a run of 1 meter northwest and $E$ represents a run of 1 meter northeast. There is a bijection between every possible path and every possible 9-letter word.

The total number of words is $2^9$ , because there are two choices for each of the 9 letters in the word.

Let a word be called valid if the path that it represents will allow both voles to cross the road.

A word is valid if and only if it is a word with no three consecutive $E$ s or $W$ s, because if this is the case, the maximum distance between the two voles would be $\sqrt{5}$ meters, which is less that 250 centimeters. Any other word will cause the voles to be 3 meters apart at some point.

To count the number of valid words, we can use a recurrence relation.

Let $WW_n$ be the number of $n$ -letter words that end with $WW$ . Let $EE_n$ , $WE_n$ , and $EW_n$ be defined similarly. Note that by symmetry, $EE_n=WW_n$ and $EW_n=WE_n$ .

The total number of valid $n$ -letter words will be $WW_n+EE_n+WE_n+EW_n$ .

To make a valid $n$ -letter word ending in $WW$ , we can add a $W$ to the end of any and every valid $(n-1)$ -letter word ending in $EW$ . This accounts for all valid $n$ -letter words ending in $WW$ .

$WW_n=EW_{n-1}$

Similarly,

$EE_n=WE_{n-1}$

Using the same logic, we can generate every $n$ -letter word ending in $EW$ by adding a $W$ to the end of any and every valid $(n-1)$ -letter word ending in either $WE$ or $EE$ .

$EW_n=WE_{n-1}+EE_{n-1}$

Knowing that $EE_n=WE_{n-1}$ , we can replace $EE_{n-1}$ in the above equation with $WE_{n-2}$ .

$EW_n=WE_{n-1}+WE_{n-2}$

Recall that $EW_n=WE_n$ . Substituting:

$WE_n=WE_{n-1}+WE_{n-2}$

To solve this recurrence we need two initial values. We can manually count all 2-letter words ( $WE$ ) and 3-letter words ( $WWE$ , $EWE$ ) to find that $WE_2=1$ and $WE_3=2$ .

This generates the Fibonacci sequence . We seek $WE_9$ , which is $F_9=34$ .

We also know that $EE_9=F_8=21$ because $EE_n=WE_{n-1}$ .

Finally, we can count the number of valid 9-letter words.

$WW_9+EE_9+WE_9+EW_9=21+21+34+34=110$

For the final probability:

$\frac{110}{2^9}=\frac{55}{256}$

$55+256=\boxed{311}$