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

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$ .

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

Problem

Solution

See also