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

Respuesta: 548

Conceptos:conteo recursivo arreglos con restricciones

Nivel de dificultad: 2890

Pista pequeña:

La condición dice que toda racha de letras idénticas tiene longitud a lo sumo $3.$ Clasifica las cadenas válidas según la longitud de su primera racha.

The condition says every run of identical letters has length at most $3.$ Classify valid strings by the length of their first run.

Pista grande:

Si $s_n$ cuenta las cadenas válidas de longitud $n$ que empiezan con una letra dada, entonces $s_n = s_{n-1} + s_{n-2} + s_{n-3}$

If $s_n$ counts valid length- $n$ strings starting with a given letter, then $s_n = s_{n-1} + s_{n-2} + s_{n-3}$

Solución:

La condición dice que toda racha máxima 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

Respuesta: 548

Nivel de dificultad: 2890

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años