Puzzles

Valid sequences of length \(n\) can be made by doing one of the following:

Therefore, the number of sequences of length \(n\) that end in B is equal to the total number of sequences of length \(n-1\); and the number of sequences of length \(n\) that end in A is equal to the number of sequences of length \(n-1\) that end in B plus the number of sequences of length \(n-2\) that end in A. Using this we see that:

The total number of valid sequences of length 11 is 638.

A valid sequence of length \(n\) can be made by either adding a single B to the right of a valid sequence of length \(n-1\) or two As to a valid sequence of length \(n-2\). Therefore, the number of sequences of length \(n\) can be calculated by adding the previous two terms (ie it's the Fibonacci sequence).

Using this, we can work out that the number of sequence of length eleven is 144.