El ABC de la creación

Tres simples reglas para un pequeño Big Bang
(Ésta es la transcripción de mi charla en el 4º Encuentro para Celebrar el Ingenio de Martin Gardner y Jaime Poniachik.)

El universo en el que transcurre este pequeño Big Bang es una cinta dividida en casillas todas iguales; es necesario aclarar que la cinta es infinita, en el sentido de que puede ser prolongada indefinidamente por cualquiera de sus dos extremos:

Este universo contiene solamente tres tipos de partículas, a las que llamaremos A, B y C. Una "ley natural" dice que cada casilla puede contener como máximo una partícula.

Hay tres reglas que rigen el modo en el que las partículas son creadas o destruidas. Estas reglas están resumidas en la siguiente imagen:

Regla 1: En dos casillas vacías consecutivas pueden colocarse dos letras iguales (en la imagen se ejemplifica con AA, pero también puede ser BB o CC).

Regla 2: Es la inversa de la anterior; dos letras iguales consecutivas pueden ser borradas (como antes, en la imagen se ejemplifica con AA, pero también puede ser BB o CC):

Reglas 3: Dos letras diferentes consecutivas pueden ser reemplazadas por la tercera letra, es decir, las dos letras se borran y el lugar que ocupaba una de ellas pasa a ser ocupado por la otra letra. En la imagen se ejemplifica el reemplazo de AB por C, pero también vale para reemplazar BA por C, CA por B, AC por B, etc.

Veamos un ejemplo de aplicación de las reglas:

En el ejemplo hemos partido del universo vacío y hemos llegado a la configuración A-espacio-B-espacio-C. Esto se ha conseguido en seis pasos; un "paso" consiste siempre en la aplicación de una de las tres reglas.

En los desafíos se parte de una cierta configuración y se debe llegar a otra, siempre en la menor cantidad posible de pasos. Los desafíos están resumidos en esta imagen:

Desafío (a): Partir del espacio vacío y llegar a ABC (sin espacios intermedios). Se entiende que al terminar la cinta sólo muestra ABC, el resto del universo está vacío. Yo lo logré en 10 pasos, pero la solución no es necesariamente la óptima. De hecho, la noche misma del encuentro Pablo Coll me aseguró que había encontrado una solución en solamente 6 pasos y que después me la enviaría.

Desafío (b): Partir de ABC y llegar a BCA; las tres letras finales no tienen por qué ocupar las mismas casillas que las iniciales. Yo lo logré en 10 pasos, pero la solución no es necesariamente la óptima.

Desafío (c): Partir de ABC y lograr que se vayan formando sucesivamente las otras cinco permutaciones posibles de esas tres letras (ACB, BCA, BAC, CAB y CBA, no necesariamente en ese orden). En su momento, cada permutación debe aparecer sola en la cinta; la cuenta de los pasos termina en el momento en que aparece la sexta permutación (sea cual fuere). Yo lo logré en 23 pasos, la solución tampoco es necesariamente la mejor.

En los dos últimos desafíos, para hacerlos más interesantes, no doy cantidades de pasos:

Desafío (d): Partir de la cinta vacía y llegar a A.

Desafío (e): Partir de A y llegar a B (la B no debe ocupar necesariamente la misma casilla que la A).

Las soluciones que lleguen (por mail o dejadas en los comentarios) serán publicadas aquí mismo, más abajo.

Gracias... ¡y que se diviertan!

Soluciones:
(a) Pablo Rowies dio en los comentarios una solución para el desafío (a) en 8 pasos que Claudio Meller, también en los comentarios, mejora a 6 pasos y Marcos Donnantuoni, a 5:
0 - - - -
1 - - AA
2 AAAA
3 A - - A
4 ABBA
5 ABC

(b) Pablo Rowies da una solución en 8 pasos para el desafío 2 que Claudio Meller mejora a 6 pasos y Marcos Donnantuoni, a 5:
0 ABC -
1 AA - -
2 AAAA
3 A - - A
4 ABBA
5 - CBA

(c) Marcos Donnantuoni y Claudio Meller encuentran soluciones con 25 pasos, tras un estudio informático Marcos aclara que la solución es óptima.
0__________ABC__
1__________ABCBB
2__________ABA_B
3__________AC__B
4__________ACBBB
5__________ACB__ *
6___________BB__
7_________BBBB__
8_________B__B__
9_________BAAB__
10________BAC___ *
11________BB____
12________BBBB__
13________B__B__
14________BCCB__
15________BCA___ *
16______CCBCA___
17______CCB_B___
18______CA__B___
19______CABBB___
20______CAB_____ *
21______CC______
22____CCCC______
23____C__C______
24____CBBC______
25____CBA_______ *

Sólo quedan abiertos los desafíos (d) y (e).

Soluciones óptimas:
Desafío (a): 5 pasos (Marcos Donnantuoni), no puede mejorarse.
Desafío (b): 5 pasos (Marcos Donnantuoni), no puede mejorarse.
Desafío (c): 25 pasos (Claudio Meller y Marcos Donnantuoni), no puede mejorarse.

Gracias por los comentarios en los que se plantean otros desafíos, en breve los incorporaré a una nueva entrada sobre el tema. Por supuesto, también agradezco los comentarios con soluciones, las que corresponde a los nuevos desafíos también aparecerán próximamente en otra entrada sobre este tema.

Éste es el video de la charla.