2020 Australian Maths Competition Senior Problem 30

Question

When I drive to school every day, I pass eight traffic lights, each either green, yellow, or red. I find that, because of synchronization, a green light is always followed immediately by a yellow, and a red light is never immediately followed by a red. Thus a sequence of lights may start with GYRY, but not RRGG. How many possible sequences of the eight lights are there?

Answer 1

I’m not good at math or English. I hope the following notations are not confusing, and my answer helps.

Let $f(n)$ represents the number of all possible sequences of $n$ lights.

If $n=0$, then the sequences are $\{ \emptyset \}$. Thus

$$ f(0) = 1 $$

If $n=1$, then the sequences are $\{ R , G, Y \}$. Thus

$$ f(1) = 3 $$

If $n=2$, then the sequences are $\{ RG, RB, GY, YR, RG, YY \}$. Thus,

$$ f(2) = 6 $$

If $n \ge 3$, then

$$\begin{align} f(n) &= f_{R}(n-1) + f_{G}(n-1) + f_{Y}(n-1)\\ &= f_{RG}(n-2) + f_{RY}(n-2) + f_{GY}(n-2) + f_{Y}(n-1)\\ &= f_{RGY}(n-3) + f_{RY}(n-2) + f_{GY}(n-2) + f_{Y}(n-1)\\ &= f(n-3) + 2f(n-2) + f(n-1)\\ \end{align} $$

I wrote a function in Python to compute the result. It told me $f(8)=595$.

Answer 2

This can be solved through recursive combinatorics, let's call:

$$G_n=\text{ valid sequences of lights long } n \text{ that terminate with G}$$ $$Y_n=\text{ valid sequences of lights long } n \text{ that terminate with Y}$$ $$R_n=\text{ valid sequences of lights long } n \text{ that terminate with R}$$

You can find out that(if you don't know how tell me and I'll help you):

$$G_{n+1}=Y_n+R_n$$ $$Y_{n+1}=G_n+R_n+Y_n$$ $$R_{n+1}=Y_{n}$$ And clearly $G_1=Y_1=R_1=1$