Acertijos

Octavo Acertijo

Se tiene un sistema formado por los siguientes símbolos: [latex]G, E, B[/latex]. Las expresiones de este sistema están formadas por combinaciones de las letras anteriores. Como en todo sistema, no toda combinación posible de símbolos es válida(por ejemplo, en matemáticas, [latex]2+2=5[/latex] es una cadena bien formada, pero no es válida). Para obtener las cadenas válidas del sistema hacen falta unos axiomas, que son las proposiciones asumidas, y unas reglas, las cuales toman premisas y devuelven una conclusión. Si estas reglas se aplican sobre los axiomas o sobre cadenas válidas devolverán cadenas válidas. Nuestro axioma es la cadena [latex]GE[/latex]. Nuestras reglas son:

  1. Si se tiene una cadena cuya última letra es [latex]E[/latex], se puede añadir una [latex]B[/latex] al final.Por ejemplo, dado [latex]BE[/latex], se puede obtener [latex]BEB[/latex].
  2. Si se tiene una cadena de la forma [latex]Gx[/latex], se tiene [latex]Gxx[/latex]. Aquí [latex]x[/latex] representa una cadena cualquiera.Algunos ejemplos: dado [latex]GEB[/latex], se puede obtener [latex]GEBEB[/latex]. Dado [latex]GBGE[/latex], se puede obtener [latex]GBGEBGE[/latex].
  3. Si en una cadena se tiene la secuencia [latex]EEE[/latex], se puede obtener una nueva cadena sustituyendo [latex]EEE[/latex] por [latex]B[/latex]. Por ejemplo, dado [latex]GEEEGB[/latex], se puede obtener [latex]GBGB[/latex].
  4. Si en una cadena se tiene la secuencia [latex]BB[/latex], se puede obtener una nueva cadena eliminando [latex]BB[/latex]. Por ejemplo, dado [latex]GBBE[/latex], se puede obtener [latex]GE[/latex].

Partiendo de nuestro axioma, [latex]GE[/latex], ¿se pueden obtener las siguientes cadenas aplicando las reglas (es decir, son válidas)?

  • [latex]E[/latex].
  • [latex]GEBBE[/latex].
  • [latex]GBEEB[/latex], con la condición de que no aparezcan más de 4 [latex]E[/latex] seguidas en ningún paso.
  • [latex]GB[/latex].

Si la respuesta es afirmativa, hay que dar los pasos para obtenerla. En caso negativo, hay que explicar por qué no se puede.

Nota: las reglas solo se pueden usar una a la vez. Por ejemplo, si se tiene [latex]GBBEBB[/latex] y se quiere obtener [latex]BE[/latex] hay que hacerlos en dos pasos, aplicando la regla 4 dos veces: [latex]GBBEBB \to GEBB \to GE[/latex].