Question

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.

Answer

Answer: 548

Concepts:recursive counting arrangements with restrictions

Difficulty rating: 2890

Solution:

The condition says every maximal run of identical letters has length at most $3.$ Let $s_n$ count the valid strings of length $n$ whose first letter is A; by symmetry the answer is $2s_{10}.$ Removing the first run (of length $1,$ $2,$ or $3$ ) leaves a valid shorter string beginning with B, so $s_n = s_{n-1} + s_{n-2} + s_{n-3}.$

Starting from $s_1 = 1,$ $s_2 = 2,$ $s_3 = 4,$ the sequence runs $7, 13, 24, 44, 81, 149, 274,$ so $s_{10} = 274.$

The number of valid strings is $2 \cdot 274 = 548.$

2015 AIME II Problem 12

Answer: 548

Difficulty rating: 2890

Solution:

Problem 12 in Other Years