Recursive (Counting) Exeter Intermediate
2015


Problem - 2046

How many length ten strings consisting of only $A$s and $B$s contain neither "$BAB$" nor "$BBB$" as a substring?


,This is equivalent to counting the cases where there are no consecutive $B$s on every other position.  In order to solve this, let's construct two substrings: one consists of the five letters at the odd positions of the original string. The other consists of the five letters at the even positions. We are going to count the cases which there are no consecutive $B$s in each of these two substrings.

By the conclusion of # 4277, the answer is $F_5=13$. Therefore, the final answer is $$13\times 13=\boxed{169}$$ 

because these two substrings are indepedent.

report an error