Question:
A frog has an equal probability of jumping left, right or staying stationary every minute. Consider the set of n-minute-long paths of the frog. Each such path
is given by an n-tuple over the set {L, R, S}, where L represents the
frog’s decision of jumping to the left, R stands for the right and S –
for staying in place.
(i) How many such paths contain no two identical consecutive steps?
For example, the path SLSRSLS is allowed, while SLLRSL is
not. [3 marks]
(ii) Assume that the frog catches a fly any time it jumps to the left
and two flies any time it jumps to the right, but it gets no more
flies when it stays in its place. In how many paths of length n the
total number of flies caught will be divisible by 3? [3 marks]
(iii) Give a recursive formula T(n) for the number of n-minute-long
paths on which the frog catches an even number of flies. Calculate T(5).
[3 marks]
(iv) In how many such paths the frog catches an even number of
flies in last two steps? [3 marks]
(v) Use your solution to part (c) to give a recursive formula F(n) for
the number of paths where the number of flies caught in last two
steps is even and the total number of flies caught along the path
is even? Calculate F(5). [3 marks]
Solution:
for part i) I understand there are 3 choices for the first path, and then 2 choices for every following movement. E.g. $3*2*2*2*…*(n-1)$ options so there are $3*2^{n-1}$ choices.
However I am struggling to understand the logic for ii)
Any guidance will be greatly appreciated as then I can continue with the follow up questions!
Best Answer
Assume $n = 1$. In this case, there are three cases for the number of flies $k$:
In order to arrive at $k \mod 3 = 0$ for $n = 2$, one and only one move can be taken from each of these states: do not move, move right, and move left, respectively. The same is true for $k \mod 3 = 1$ and $k \mod 3 = 2$, so we find three different paths for each of these. A similar reasoning can be used to extend these paths to a length of three, four, etc. In the end, we find that there are $\frac{3^n}{3} = 3^{n-1}$ paths of length $n$ for which the number of caught flies $k$ is divisible by three.
As a hint for (iii): first consider the number of paths $T_{n-1}$ of length $n - 1$ resulting in an even number of flies, and multiply by two, since there are two "even moves"; then consider the number of paths $O_{n-1} = 3^{n-1} - T_{n-1}$ of length $n - 1$ resulting in an odd number of flies, and multiply by one, since there is only one "odd move". This will result in a recurrence relation for the number of paths $T_n$, with $T_1 = 2$. Can you take it from here?