Problema 5 del segundo nivel de la Olimpiada de Mayo (2017)
Se dirige a una edad de: 14 años

Ababa juega con una palabra formada con las letras de su nombre, y se ha puesto ciertas reglas:

Si encuentra una A seguida inmediatamente por una B, las puede sustituir por BAA.

Si encuentra dos B consecutivas, las puede borrar.

Si encuentra tres A consecutivas, las puede borrar.

Ababa empieza con la palabra ABABABAABAAB.

Con las reglas anteriores ¿Cuántas letras tiene la palabra más corta a la que puede llegar?

¿Por qué no puede llegar a una palabra más corta?

Solución:

En este ejercicio se valora la capacidad de seguir reglas, adaptarse, y poder generalizar a partir de esas reglas.

Jugando con unas cuantas palabras, podemos deducir casos generales, por ejemplo (pongo paréntesis cuando hago una sustitución, para que se note):

ABABA
(BAA)ABA
B()BA
()A

Observaremos rápidamente que en todas las operaciones, la cantidad de letras B o permanece constante, o bien disminuye en 2, por lo que mantienen su paridad. Puesto que en la palabra inicial hay 5 letras B, como mínimo debe quedar una B en cualquier palabra que tengamos.

Si nos fijamos en las A, jugando con varias palabras, descubriremos que desaparecen de tres en tres, y podemos cambiar una a la izquierda de una B por dos a la derecha, de forma que si tenemos dos a la izquierda, podemos cambiar por cuatro a la derecha, y por tanto por una a la derecha.

En la palabra inicial, ABABABAABAAB, todas las A se pueden cambiar, puesto que hay letras B a la derecha que pueden servir para la conversión. Para juntar tres letras A, que puedan desaparecer necesitaremos una A a cada lado de una B, o bien anular dos A con una A que tengan dos B entre ellas.

Lo que se puede decir es que, dependiendo de cuántas B tengan a la derecha (una o cero, ya que al final quitaremos las B a pares), cada A vale por una o por dos, pero si obtenemos tres, es como si no hubiese ninguna. Además, si tenemos dos a la izquierda es como si tenemos una a la derecha.

Contando las letras iniciales, y decidiendo que van a quedar a la derecha del todo, por ejemplo, tenemos que la primera A vale por dos, la segunda por uno, la tercera por dos, las dos siguientes por uno, y las dos siguientes, cada una por dos, de forma que tendríamos 2 + 1 + 2 + 2 + 4 = 11, lo que indica un total de dos letras A a la derecha, o lo que es lo mismo, una única A a la izquierda.

Por lo tanto, deben quedar al menos dos letras: una A a la izquierda y una B. Es imposible que queden menos con esa configuración inicial.

Un ejemplo de cómo conseguirlo efectivamente sería el siguiente (hay varios modos equivalentes):

ABABABAABAAB
(BAA)ABABAABAAB
BB()ABAABAAB
()ABAABAAB
(BAA)AABAAB
B()ABAAB
B(BAA)AAB
()()AB