Problem:
There are 210=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:
Let ak​,bk​, and ck​ be the number of acceptable strings of length k that begin with exactly 1,2, or 3 of the same letter, respectively. For k≥3,bk+1​=ak​, ck+1​=bk​, and ak+1​=ak​+bk​+ck​=ak​+ak−1​+ak−2​. Using the fact that a1​=2,a2​=2, and a3​=4, the recursion can be used to find the first 11 terms of the sequence an​ to be 2,2,4,8,14,26,48,88,162,298, and 548. The number of strings of length 10 that satisfy the requirement is a10​+b10​+c10​=a11​=548​.
The problems on this page are the property of the MAA's American Mathematics Competitions