AMC 12 Mock Exam 3 Problem 16

Problem 16 of 25

A string of letters, each $A$ or $B$ , is called odd-blocked if every maximal block of consecutive identical letters has odd length. For example, $ABBBA$ and $BAAAAAB$ are odd-blocked, but $AABAB$ is not. How many odd-blocked strings of length $12$ are there?

Show solution

Solution

An odd-blocked string is determined by its first letter ( $2$ choices) and the ordered list of its block lengths, which is a composition of $12$ into odd parts (the letters then alternate).

Let $c_n$ be the number of compositions of $n$ into odd parts. If the last part is $1$ , removing it leaves a composition of $n-1$ ; if the last part is at least $3$ , reducing it by $2$ leaves a composition of $n-2$ ; both maps are bijections. So $c_n=c_{n-1}+c_{n-2}$ with $c_1=c_2=1$ , the Fibonacci numbers: $c_{12}=144$ . The answer is $2\cdot144=\boxed{288}$ .

Tagged: recursive counting: strings with odd runs

Answer choices

Solution