2015 AIME II Problems/Problem 12

Problem

There are 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

(so sorry I still haven't gotten Latex, will get it soon)

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.