Solución a las reglas de ababa

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

Published by

dimates

Grupo de divulgación matemática de la Universidad de Alicante

Deja un comentario

Tu dirección de correo electrónico no será publicada.