[ Geometric progression $]$ $[$ Classical combinatorics (other). ]

A frog jumps from vertex to vertex of a hexagon $A B C D E F$, each time moving to one of the adjacent vertices.

a) In how many ways can it get from $A$ to $C$ in $n$ jumps?

b) The same question, but with the condition that it cannot jump to $D$?

## Frog-Miner.

c) Suppose the frog's path starts at vertex $A$, and there is a mine at vertex $D$. Every second, it makes another jump. What is the probability that it will still be alive after $n$ seconds?

d)* What is the average lifespan of such frogs?
a) It is clear that after an even number of jumps, the frog can only be at vertices $A, C$ or $E$.

Let $a_{k}, c_{k}, e_{k}$ denote the number of paths of length $2k$ leading from $A$ to $A, C$, and $E$ respectively. By symmetry, $c_{k} = e_{k}$. It is easy to see that the following equalities hold: $c_{k+1} = a_{k} + 3c_{k}$, $a_{k+1} = 2a_{k} + 2c_{k}$.

From this, we have $c_{k+2} = a_{k+1} + 3c_{k+1} = 2a_{k} + 2c_{k} + 3c_{k+1} = 2(c_{k+1} - 3c_{k}) + 2c_{k} + 3c_{k+1} = 5c_{k+1} - 4c_{k}$.

From the initial conditions $c_{0} = 0, c_{1} = 1$, we find $c_{k} = \frac{1}{3}(4^{k} - 1)$ (this is not difficult to prove by induction).

b) Keeping the notation $c_{k}$ from part a) (now this number will be different). Let $b_{k}$ denote the number of paths of length $2k-1$ leading from $A$ to $B$. Then $b_{k+1} = 3b_{k}$ (in two jumps, one can return to $B$ from $B$ in two ways and reach $F$ from $B$ in one way). But $c_{k} = b_{k}$, so $c_{k+1} = 3c_{k}$ for $k > 0$. As before, $c_{1} = 1$, hence $c_{k} = 3^{k-1}$.

c) Since $D$ can only be reached on an odd jump, the probability that the frog will be alive after $2k$ seconds is equal to the probability that it is alive after $2k-1$ seconds. Let the latter probability be denoted by $P_{k}$. At this moment, it is in $B$ or $F$. After two jumps, it will land in $D$ with probability $1/4$ and remain alive with probability $3/4$. Therefore, $P_{k+1} = 3/4 P_{k}$.

Since $P_{1} = 1$, it follows that $P_{k} = (3/4)^{k-1} (k \geq 1)$.

d) As seen from part c), the probability of landing in $D$ exactly after $2k+1$ seconds is $1/4 \cdot (3/4)^{k-1}$.

Therefore, the average lifespan of the frog is the sum of the series $N = \sum_{k=1}^{\infty} (2k+1) \cdot \frac{3^{k-1}}{4^{k}}$.

This sum can be computed using the generating function

$f(t) = \frac{1}{3} \cdot \sum_{k=1}^{\infty} \frac{3^{k}}{4^{k}} t^{2k+1} = \frac{t^{3}}{4} \cdot \sum_{k=0}^{\infty} \left(\frac{3t^{2}}{4}\right)^{k} = \frac{t^{3}}{4 - 3t^{2}}$

Indeed, $N = f'(1) = 9$.

## Answer

a) $\frac{1}{3}(2^n - 1)$ ways for even $n$; cannot reach for odd $n$. b) $3^{n/2-1}$ ways for even $n$; cannot reach for odd $n$.

c) $(3/4)^{k-1}$ for $n = 2k-1$ and for $n = 2k (k \geq 1)$. d) 9 seconds.