Question

Hay $2^{10} = 1024$ posibles cadenas de $10$ letras en las que cada letra es una A o una B. Halla el número de tales cadenas que no tienen más de $3$ letras adyacentes idénticas.

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.

Respuesta

Solución:

La condición dice que toda racha maximal de letras idénticas tiene longitud a lo sumo $3.$ Sea $s_n$ el número de cadenas válidas de longitud $n$ cuya primera letra es A; por simetría la respuesta es $2s_{10}.$ Quitar la primera racha (de longitud $1,$ $2,$ o $3$ ) deja una cadena válida más corta que empieza con B, así que $s_n = s_{n-1} + s_{n-2} + s_{n-3}.$

Partiendo de $s_1 = 1,$ $s_2 = 2,$ $s_3 = 4,$ la sucesión sigue $7, 13, 24, 44, 81, 149, 274,$ así que $s_{10} = 274.$

El número de cadenas válidas es $2 \cdot 274 = 548.$

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 Problema 12

Solución:

El Problema 12 en otros años