, 2014

Solution:

Answer: 0.9102805441016536

First, we establish a rough upper bound for the probability $p$. Let $q$ be the probability that the frog can reach the lily pad at the point $2014$ on the number line if it is allowed to jump from a point $n$ on the number line to the point $n+1$, in addition to the points $n+2$ and $n+3$. Clearly, $p \leq q$. Furthermore, $p$ is approximated by $q$; it should be easy to convince one's self that jumps from a point $n$ to the point $n+1$ are only useful for reaching the lily pad at point $2014$ in very few situations.

Now we compute $q$. We note that, if the frog can jump from points $n$ to points $n+1, n+2$, and $n+3$, then it can reach the lily pad at the point $2014$ on the number line if and only if each snake-free lily pad is at most $3$ units away from the closest snake-free lily pad on the left.

Define the sequence $\left\{a_{m}\right\}_{m=1}^{\infty}$ by $a_{0}=1, a_{1}=1, a_{2}=2$, and $a_{m+3}=a_{m+2}+a_{m+1}+a_{m}$ for $m \geq 0$. Then, it can be shown by induction that $a_{m}$ is the number of possible arrangements of snakes on lily pads at points $1, \cdots, m-1$ so that the frog can make some sequence of jumps (of size $1,2$, or $3$) from the lily pad at point $0$ to the lily pad at point $m$ without landing on a lily pad containing a snake. It follows that $q=a_{2014} / 2^{2013}$. So

$$p^{1 / 2014} \approx q^{1 / 2014}=\left(a_{2014}\right)^{1 / 2014} / 2^{2013 / 2014} \approx\left(a_{2014}\right)^{1 / 2014} / 2$$

Analyzing the recurrence relation $a_{m+3}=a_{m+2}+a_{m+1}+a_{m}$ yields that $\left(a_{2014}\right)^{1 / 2014}$ is approximately equal to the largest real root $r$ of the characteristic polynomial equation $r^{3}-r^{2}-r-1=0$. So to roughly approximate $p$, it suffices to find the largest real root of this equation.

For this, we apply Newton's method, or one of many other methods for computing the roots of a polynomial. With an initial guess of $2$, one iteration of Newton's method yields $r \approx 13 / 7$, so $p \approx r / 2 \approx 13 / 14 \approx 0.928571$. A second iteration yields $r \approx 1777 / 966$, so $p \approx r / 2 \approx 1777 / 1932 \approx 0.919772$. (It turns out that the value of $r$ is $1.839286 \ldots$, yielding $p \approx r / 2=0.919643 \ldots$.)

Using tools from probability theory, we can get an even better estimate for $p$. We model the problem using a discrete-time Markov chain. The state of the Markov chain at time $n$, for $n=0,1, \ldots, 2013$, indicates which of the lily pads at positions $n-2, n-1, n$ are reachable by the frog. It is clear that the state of the Markov chain at time $n$ only depends (randomly) on its state at time $n-1$. There are $2^{3}=8$ possible states for this Markov chain, because each of the lily pads at positions $n-2, n-1, n$ can be either reachable or unreachable by the frog. Number each state using the number $1+d_{2}+2 d_{1}+4 d_{0}$, where $d_{i}$ is $1$ if the lily pad at point $n-i$ is reachable, and $0$ otherwise. So, for example, at time $n=0$, the lily pad at point $n$ is reachable $\left(d_{0}=1\right)$ whereas the lily pads at points $n-1$ and $n-2$ are unreachable $\left(d_{1}=d_{2}=0\right)$, so the Markov chain is in state number $1+d_{2}+2 d_{1}+4 d_{0}=5$.

The transition matrix $M$ for the Markov chain can now be computed directly from the conditions of the problem. It is equal to

$$M:=\left[\begin{array}{cccccccc} 1 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \end{array}\right] .$$

(The verification of this transition matrix is left as an exercise for the reader.) So the state vector $v$ for the Markov chain at time $2013$ is
$$v:=M^{2014}[0,1,0,0,0,0,0,0]^{t}$$

Now, the lily pad at point $2014$ is reachable by the frog if and only if the Markov chain is in state $3,4,5,6,7$, or $8$ at time $2013$. This happens with probability
$$p=[0,0,1,1,1,1,1,1] v$$

By expanding $[0,1,0,0,0,0,0,0]^{t}$ in an eigenbasis for $M$, we find that $p^{1 / 2014}$ is approximately equal to the second-largest real eigenvalue of the matrix $M$. The characteristic polynomial of $M$ is
$$\operatorname{det}(\lambda I-M)=-\frac{\lambda^{3}}{8}+\frac{3 \lambda^{4}}{8}+\frac{\lambda^{6}}{4}-\frac{3 \lambda^{7}}{2}+\lambda^{8}$$
so its eigenvalues are the roots of this polynomial. The largest real root of this characteristic polynomial is $\lambda=1$, and the second-largest real root is $0.9105247383471604 \ldots$ (which can be found, again, using Newton's method, after factoring out $(\lambda-1) \lambda^{3}$ from the polynomial), which is a good approximation for $p$.