Mostrando entradas con la etiqueta El ABC de la creación. Mostrar todas las entradas
Mostrando entradas con la etiqueta El ABC de la creación. Mostrar todas las entradas

El ABC de la creación (3): imposibilidades

Pares y nones
Las reglas del juego y los primeros desafíos pueden verse en este enlace, otros desafíos pueden verse en este otro enlace.

De los dos últimos desafíos planteados en la entrada original, uno de ellos pedía pasar de la cinta vacía a una que contuviera solamente la letra A, y el otro desafío, pasar de la letra A a la letra B. En los comentarios a esa misma entrada Marcos Donnantuoni conjeturó que estos objetivos son imposibles de alcanzar; mi intención aquí es demostrar que, en efecto, son imposibles.

La demostración de ambas imposibilidades pasa por un argumento de paridad. Recordemos que la primera regla dice que donde haya dos casillas vacías es posible "crear" dos letras iguales; la segunda regla enuncia la operación inversa, dos letras iguales y consecutivas pueden ser borradas. La tercera regla dice que dos letras diferentes consecutivas (AB, por ejemplo) pueden ser cambiadas por la letra restante (en el ejemplo, una C).

Pensemos ahora en las cantidades de letras que haya en la configuración inicial, y específicamente fijémonos en sus paridades. Las dos primeras reglas no alteran la paridad de esas cantidades, ya le suman o le restan un 2 a una de ellas. La tercera regla, en cambio, cambia las tres paridades a la vez, ya que le suma un 1 a una cantidad y le resta 1 a las otras dos. Es decir, al aplicar cualquiera de las reglas, o bien las tres paridades no cambian, o bien cambian todas a la vez.

Esto significa que, si al comenzar, las cantidades de dos de las letras tenían la misma paridad (ambas cantidades eran pares o ambas eran impares) entonces a lo largo de todo el proceso esas cantidades seguirán teniendo la misma paridad (porque, en caso de cambiar, ambas paridades cambiarán al mismo tiempo); y si esas dos cantidades, al comenzar, tenían diferente paridad entonces la paridad seguirá siendo siempre diferente (por la misma razón). Podemos decir, en resumen, que las paridades relativas de las cantidades de letras no cambiarán nunca.

Ahora bien, si quisiéramos pasar de la cinta vacía a la letra A entonces al comenzar las cantidades de A y de B tendrían la misma paridad (ambas cantidades serían pares, ya que valen cero), mientras que al terminar habría una cantidad impar de A (una letra) y una cantidad par de B (cero). La paridad relativa de A y B habría cambiado, lo cual es imposible. Luego, no puede pasarse de la cinta vacía a una sola A. Lo mismo sucede si queremos pasar de A a B, porque al comenzar A y C tendrían diferente paridad (uno y cero son las cantidades iniciales de esas letras), pero al terminar tendrían la misma (cero y cero, ambas pares).

Una pregunta que queda pendiente es si vale la afirmación recíproca; es decir, si tenemos dos configuraciones de letras en las cuales las paridades relativas de A, B y C son las mismas (es decir, dos paridades que sean iguales/diferentes en una configuración son también iguales/diferentes en la otra configuración) entonces ¿es siempre posible pasar de una configuración a la otra? Creo que la respuesta es que sí, aunque no he podido encontrar una demostración elegante de ese hecho.

El ABC de la creación (2): soluciones y nuevos desafíos.

Espacio versus tiempo
Las reglas del juego y los primeros desafíos pueden verse en este enlace

Marcos Donnantuoni propone una variante para todos los desfíos que consiste en buscar la solución que ocupe el menos espacio posible, en lugar del menor tiempo. Es decir, ahora buscamos la solución que pueda ser desarrollada en la cinta de menor longitud (a igualdad en espacio, será mejor la solución en menor tiempo).

Éstas son, hasta ahora, las mejores soluciones para los tres primeros desafíos en esta variante.

(a) Pasar de la cinta vacía a ABC y (b) pasar de ABC a BCA: Las soluciones óptimas en tiempo (ambas de Marcos, con 5 pasos) son también hasta ahora las mejores en espacio, con 4 espacios cada una (no parece que se pueda mejorar). Las copio aquí:
0 ----
1 --AA
2 AAAA
3 A--A
4 ABBA
5 ABC-

0 ABC-
1 AA--
2 AAAA
3 A--A
4 ABBA
5 -CBA

(c) A partir de ABC recorrer las otras cinco permutaciones de esas letras: MFR tiene una solución en 25 pasos (óptima en tiempo) que sólo usa 5 espacios (la de Marcos, también de 25 pasos, pblicada en el entrada anterior, si no conté mal -y pude haber contado mal- usa 10 espacios):
00   ABC--
01   C-C--
02   C-CAA
03   C--BA
04   CCCBA
05   --CBA
06   --C-C
07   BBC-C
08   BA--C
09   BACCC
10   BAC--
11   B-B--
12   B-BAA
13   B--CA
14   BBBCA
15   --BCA
16   --B-B
17   AAB-B
18   AC--B
19   ACBBB
20   ACB--
21   -BB--
22   -BBBB
23   -B--B
24   -BAAB
25   --CAB

Dos nuevos desafíos:

El caminante (propuesto por Leonardo): pide hacer "caminar" una letra A n pasos hacia la derecha o hacia la izquierda. MFR pudo hacer "caminar" una A una cantidad par n de casillas, a la izquierda o a la derecha, en exactamente n pasos; por ejemplo para = 4:

00   A----
01   AAA--
02   --A--
03   --AAA
04   ----A

"Para moverla sólo un lugar", dice MFR, "cuesta un poquito más de trabajo, a mí me salió en 5 pasos (y utilizando dos 'espacios' adicionales en sentido opuesto al que queremos 'avanzar')":
00   --A-
01   BBA-
02   BC--
03   BCAA
04   BB-A
05   ---A

Leonardo, por su parte, tiene una solución para mover A un paso a la derecha en 3 tiempos (y 4 espacios):
00 -A--
01 -ABB
02 --CB
03 --A-

Actualización del 15.11.13: Escribe Leonardo en los comentarios.
Conclusiones sobre traslados de A:
Para cualquier número n de pasos, con n par, la cantidad mínima es n. 
Para cualquier número n de pasos, con n impar, la cantidad mínima es n+2.
Por otra lado, y como consecuencia de esto, dado un número n cualquiera, si se lo escribe de la forma q+w, siendo q y w enteros positivos, entonces la cantidad de pasos necesarios para moverlo n lugares será igual a la de q sumada a la de w.
En otras palabras, si definimos una función P(n) que es la mínima cantidad de pasos necesarios para trasladar una A n lugares, entonces P(n)=P(q+w)=P(q)+P(w) siempre que q+w=n.

Desafío escatológico (propuesto por Marcos): pide pasar de BABA a CACA...
...(1) en la menor cantidad de tiempo
...(2) usando el menor espacio.

Claudio Meller tiene una solución en 7 pasos y 6 espacios, y otra en 8 pasos y 5 espacios.
7 PASOS  SEIS ESPACIOS
0. --BABA
1. CCBABA
2. CA-ABA
3. CA--CA
4. CACCCA
5. CAC--A
6. CACAAA
7. CACA

8 PASOS CINCO ESPACIOS
0. -BABA
1. --CBA
2. CCCBA
3. C--BA
4. CAABA
5. CA-CA
6. CA--B
7. CACCB
8. CACA-

La solución ¿óptima? de Marcos tiene 6 pasos y 5 espacios:
0 BABA-
1 BAC--
2 BACAA
3 B - BAA
4 B--CA
5 BAACA
6 -CACA

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.