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 n = 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.

Arquímedes y el infinito

Arquímedes en la bañera

Durante siglos se creyó que el libro El Método, obra de Arquímedes de Siracusa (ca. 287-212 a.C.) estaba irremediablemente perdido. Se sabía, por diversas referencias, que en este libro el autor describía los razonamientos físicos que le habían permitido conjeturar los teoremas geométricos que después demostraba con todo rigor lógico en sus otros libros. Sin embargo, el contenido exacto de la obra permaneció desconocido hasta 1906 cuando, para gran sorpresa de todos, se descubrió en Estambul una copia de la obra. Se trataba en realidad de un palimpsesto, es decir, un códice escrito en pergamino que había sido borrado, por suerte imperfectamente, y reutilizado para escribir un manuscrito diferente. Las técnicas de 1906 permitieron reconstruir una parte de la obra original, pero varios fragmentos no pudieron ser recuperados en aquel momento.

El trabajo recomenzó a principios del siglo XXI, cuando un grupo de expertos, utilizando técnicas modernas de iluminación y de análisis de imágenes, lograron avanzar en el desciframiento de El Método. Parte de lo que descubrieron estos expertos sugiere que Arquímedes trabajó explícitamente con el infinito en acto. La historia está narrada en El Código de Arquímedes, libro de R. Netz y W. Noel. Según estos expertos, para comparar el volumen de dos cuerpos, Arquímedes los suponía cortados en infinitas lonjas de ancho infinitamente pequeño y concluía que ambos volúmenes era iguales porque era posible emparejar las tajadas que formaban uno de ellos con las tajadas que formaban al otro; si estas conclusiones son correctas esto implicaría que Arquímedes trabajó con la comparación entre dos conjuntos infinitos mediante el emparejamiento de sus componentes siglos antes de que Cantor hiciera lo mismo.

Ocean: Assessing the effect of climate change on upwelling ecosystems

Ocean: Assessing the effect of climate change on upwelling ecosystems
Assessing the effect of climate change on upwelling ecosystems is essential to be able to predict the future of marine resources. The zones concerned by this upwelling of cold deep water, which is very rich in nutrients, provide up to 20 % of global production of fish. ...

El ácido sulfhídrico ‘amenaza’ las praderas de Posidonia

La acumulación de ácido sulfhídrico en el fondo marino es uno de los factores que más amenazan la supervivencia de Posidonia oceanica, una especie endémica del Mediterráneo. Así lo ha constatado un equipo con participación del Consejo Superior de Investigaciones Científicas (CSIC) que ha estudiado durante ocho años las praderas que forma esta planta en las Islas Baleares. Los resultados, publicados en la revista Global Change Biology, determinan que el aumento de la temperatura máxima de la superficie del mar está relacionado con un mayor estrés de la especie por sulfhídrico. Según los científicos, el aumento de la temperatura promueve la descomposición de la materia orgánica y, por tanto, la acumulación de ácido en los sedimentos en condiciones de falta de oxígeno. Simultáneamente, el aumento de la temperatura intensifica la respiración de la planta y, por tanto, su capacidad para mantener los tejidos oxigenados. El sulfhídrico puede entonces penetrar en la planta a través de las raíces y llegar a causar un estrés tóxico y, en algunos casos, la muerte. “Se sabe que la Posidonia  es muy vulnerable al ácido sulfhídrico, incluso aunque las concentraciones sean bajas. Un aporte importante de materia orgánica resultado de la contaminación humana afectará a la supervivencia de esta especie”, destaca Rosa García, investigadora del CSIC en el Instituto Mediterráneo de Estudios Avanzados, mixto del CSIC y la Universidad de las Islas Baleares. Los investigadores han medido las tasas netas de crecimiento de la población en cada pradera y el isótopo estable de azufre, indicador de la acumulación del sulfhídrico, en muestras de hojas, sedimento y agua. “Con estos parámetros hemos calculado el porcentaje de azufre presente en la planta que proviene del ácido sulfhídrico acumulado en el sedimento. Además, hemos utilizado el isótopo de azufre como indicador de toxicidad en las hojas. También hemos relacionado los datos de azufre con una serie temporal de temperaturas máximas anuales del agua del mar recopiladapara las diferentes islas, la profundidad de las praderas y las tasas de crecimiento”, ha detallado García. Según el estudio, a mayor profundidad las praderas están menos expuestas al estrés por sulfhídrico. No obstante, los científicos prevén que la profundidad no será suficiente para paliar las consecuencias de las temperaturas proyectadas para finales del siglo XXI, incluso aunque se tengan en cuenta escenarios moderados de emisión de gases de efecto invernadero. “Uno de los escenarios modela el estrés por azufre en un gradiente de 40 metros de profundidad a la temperatura máxima estimada en el mar Mediterráneo para finales del siglo XXI. El modelo predice que las praderas de Posidonia estarían afectadas por el estrés por sulfhídrico hasta los 40 metros de profundidad,  exacerbando así el declive de la especie y comprometiendo su supervivencia”, agrega la investigadora del CSIC. Una especie desprotegida Desde principios del siglo XX, entre el 5% y el 20% del área cubierta por Posidonia oceanica se ha perdido debido principalmente al impacto humano. El calentamiento global ha emergido en los últimos años como una amenaza para esta especie de crecimiento extremadamente lento y con una longevidad milenaria. En Baleares, las plantas que pueblan los fondos marinos se encuentran actualmente en regresión, no sólo por el calentamiento del agua, sino también por perturbaciones locales como la contaminación o los anclajes de las embarcaciones. Estudios previos han revelado que la densidad de la especie podría disminuir un 90% a mediados de este siglo debido al calentamiento del agua superficial del mar Mediterráneo. Entre los beneficios ecosistémicos que podrían llegar a desaparecer, destaca el enterramiento de dióxido de carbono, el reciclado de nutrientes, la protección costera de la erosión y el aumento de la biodiversidad. Referencia Bibliogáfica Rosa García, Marianne Holmer, Carlos M. Duarte, Núria Marbà. Global warming enhances sulphide stress in a key seagrass species (NW Mediterranean). Global Change Biology. DOI: 10.1111/gcb.12377