2015 AIME II Problems/Problem 12

Problem

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.

Solution 1

The solution is a simple recursion:

We have three cases for the ending of a string: three in a row, two in a row, and a single:

...AAA $(1)$ ...BAA $(2)$ ...BBA $(3)$

For case $(1)$ , we could only add a B to the end, making it a case $(3)$ . For case $(2)$ , we could add an A or a B to the end, making it a case $(1)$ if you add an A, or a case $(3)$ if you add a B. For case $(3)$ , we could add an A or a B to the end, making it a case $(2)$ or a case $(3)$ .

Let us create three series to represent the number of permutations for each case: $\{a\}$ , $\{b\}$ , and $\{c\}$ representing case $(1)$ , $(2)$ , and $(3)$ respectively.

The series have the following relationship:

$a_n=b_{n-1}$ ; $b_n=c_{n-1}$ ; $c_n=c_{n-1}+a_{n-1}+b_{n-1}$

For $n=3$ : $a_3$ and $b_3$ both equal $2$ , $c_3=4$ . With some simple math, we have: $a_{10}=88$ , $b_{10}=162$ , and $c_{10}=298$ . Summing the three up we have our solution: $88+162+298=548$ .

Solution 2

This is a recursion problem. Let $a_n$ be the number of valid strings of $n$ letters, where the first letter is $A$ . Similarly, let $b_n$ be the number of valid strings of $n$ letters, where the first letter is $B$ .

Note that $a_n=b_{n-1}+b_{n-2}+b_{n-3}$ for all $n\ge4$ .

Similarly, we have $b_n=a_{n-1}+a_{n-2}+a_{n-3}$ for all $n\ge4$ .

Here is why: every valid strings of $n$ letters $(n\ge4)$ where the first letter is $A$ must begin with one of the following:

$AAAB$ - and the number of valid ways is $b_{n-3}$ .

$AAB$ - and the number of valid ways is $b_{n-2}$ .

$AB$ - and there are $b_{n-1}$ ways.

We know that $a_1=1$ , $a_2=2$ , and $a_3=4$ . Similarly, we have $b_1=1$ , $b_2=2$ , and $b_3=4$ . We can quickly check our recursion to see if our recursive formula works. By the formula, $a_4=b_3+b_2+b_1=7$ , and listing out all $a_4$ , we can quickly verify our formula.

Therefore, we have the following:

$\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c}Value of n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\\hline a & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\\b & 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274\end{tabular}$

The total number of valid $10$ letter strings is equal to $a_{10}+b_{10}=274+274=\boxed{548}$ .

Notice that $a_n = b_n$ , since $a_1=b_1$ , $a_2=b_2$ , and $a_3=b_3$ . Therefore, we didn't really need to list out both recursion formulas, which could save us some time.

Note

This problem has the same general approach as #22 on the 2015 AMC 12A.

2015 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 11	Followed by Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2015 AIME II Problems/Problem 12

Contents

Problem

Solution 1

Solution 2

Note

See also