Un problemilla para hacer a oscuras.
Un problema ni demasiado sencillo ni demasiado complicado.
Ideal para un vuelo de avión o para meditarlo con los ojos cerrados.
Este problema trata exclusivamente de cadenas formadas por las letras A y B. Es decir, expresiones de la forma ABBBABBBBAAABBBA, por ejemplo.
Dadas dos cadenas, x, y, llamo x+y al hecho de pegar la cadena x con la cadena y.
Por ejemplo, si x=AABB, y=BA entonces x+y=AABBBA.
Además, si x es una cadena, x’ es la cadena puesta del revés. Es decir, si x=ABB entonces x’=BBA.
Las cadenas (por algún criterio que no menciono) se clasificarán en aceptables y no aceptables.
Pero sabemos lo siguiente:
Si x, y son cadenas aceptables x+y es aceptable.
Las cadenas AA y B son aceptables.
Si x+y es aceptable y también x es aceptable entonces la cadena y es aceptable.
Si x es aceptable entonces x’ es aceptable.
La cadena A no es aceptable.
El problema consiste en demostrar que una cadena es aceptable si y sólo si tienen un número par de letras A.
2 comentarios
PCRdeG -
Igual alguien le puede echar una mano.
En cualquier caso una pista...que probablamente ya sabrá: Use la inducción.
Milady -
Al leerlo la primera vez me pareció muy obvio, pero luego le doy vueltas siempre a lo mismo.
¿Puedo pedir un comodín? Gracias...