Aros chinos, Baguenodier (o Baguenaudier), Meleda, Talåmodsspel, Aros de Cardano, Sello de Salomón, Chiye no wa (anillos de la ingenuidad, este último nombre engloba todo un tipo de puzzles basados en este), Ryou-kaik-Tjyo (instrumento para retrasar al invitado), (perdón si las transliteraciones quedan mal, pero es lo que he encontrado en los libros que he consultado). Tantos nombres para un mismo puzzle demuestran que la historia del mismo es muy larga. Tanto, que algunos afirman que el verdadero puzzle es encontrar el origen del juego.
Para este puzzle haré dos entradas al blog. Una para comentar algo de su historia y su análisis y otra para ver variantes. Esta entrada ha quedado un poco larga y con algunas matemáticas (si no gustas, salta lo que creas conveniente :)
Muchas veces se le atribuye a los aros chinos orígenes antiquísimos y exóticos basados más en leyendas que en datos históricos. Pero lo cierto es que se desconoce totalmente el origen. La primera referencia histórica documentada aparece en “De Viribus Quantitatis” de Luca Pacioli (1509).
(“Puede leerse” aquí en el capítulo CVII https://archive.org/details/DeViribusQuantitatis/page/n449/mode/2up )
Hasta 1997 no se conocía esta primera referencia al puzzle ya que el único manuscrito en que aparece estaba en manos de un anticuario. En esa fecha se publicó una transcripción del texto y esa es la razón de que las fuentes anteriores a 1997 no mencionen este manuscrito de Pacioli.
La fuente que más a menudo aparece como la primera mención escrita de este juego es “De Subtilitate Rerum” de Girolamo Cardano, publicado en 1550 (unos 40 años después que el manuscrito de Pacioli).
(“Puede leerse” aquí https://archive.org/details/immagineDE295MiscellaneaOpal/page/n813/mode/2up
y traducido al inglés también aquí: https://archive.org/details/cardano-the-de-subtilitate/page/752/mode/2up )
En ambos casos la descripción que se hace del juego no deja dudas de que se trata del puzzle que actualmente se conoce como los aros chinos. También en ambos casos se comenta la solución sin apoyos gráficos y usando antes o después argumentos recursivos.
Si lo analizamos como puzzle, la verdad es que tampoco tiene demasiado misterio en el sentido de que es bastante fácil comprender la mecánica y conseguir resolverlo. Digamos que es un juego “lineal”, porque en cada momento sólo hay dos movimientos posibles uno te lleva en la dirección de la solución y otro todo lo contrario (a un callejón sin salida que nos obliga a desandar el camino). Aun así, el puzzle tiene algo que lo hace “adictivo” y además es bueno estar muy familiarizado con él ya que se usa como base en muchos otros puzzles.
Lo que sí tiene, en mi opinión, es un gran interés matemático. Prueba de ello es que lo han analizado los mencionados Pacioli y Cardano, además de John Wallis, G.C. Lichtengerg, L. Gros (que, aunque creo que no era matemático, fue fundamental en la introducción del código binario en la resolución de este puzzle), Edouart Lucas y Martin Gardner (otro no matemático, pero sobradamente notable para esta ciencia) y tantos y tantos anónimos.
El juego.
Para describir el juego, nosotros nos podemos apoyar en imágenes, mucho más versátil que los textos de Cardano y Pacioli. Y aún así se hace difícil de entender si no lo has manejado. El juego consta de dos partes que tienen que acabar separándose. Por un lado una especie de bastidor alargado (abajo en color verde) que suele llevar una empuñadura para manejarlo y por otro una base también alargada (abajo en color rosa) con unas varillas y anillas “entrelazadas” como se indica en el siguiente dibujo:
Como se puede apreciar en el dibujo anterior, cada anilla está sujeta por una pieza vertical (aquí en negro) que suele ser rígida (aunque yo lo fabriqué flexible). Esa pieza vertical está unida a la anilla permitiendo el movimiento de la misma, atraviesa la base y se puede también mover arriba y abajo respecto de la base. Cada uno de esos “postes” verticales no puede separarse de la base ya que tiene algún tipo de tope en la parte inferior y en la superior está la anilla. Las anillas y los postes están entrelazadas como se indica en el dibujo, de modo que cada poste pasa por el interior de la anilla que tiene a su izquierda. Se suele nombrar como primera anilla la que no rodea ningún poste, aquí situada a la derecha y unida al poste A.
En la siguiente imagen he puesto un ejemplo de una posición en la que nos podríamos encontrar el puzzle. Aunque se puede confundir qué líneas pasan por delante o por detrás de otras, espero que pueda distinguirse cómo es la unión de las dos partes del juego.
En esa posición he dejado de color azul las anillas que se suele considerar que están “fuera” del bastidor verde y en color rojo las anillas que están “dentro”. Se puede ver que los postes B y E (recuerda que los postes van en negro) pasan por el interior del bastidor (verde) y al mismo tiempo las anillas de esos postes “rodean” el bastidor. De modo que, aunque intentáramos sacar el bastidor hacia la izquierda, el poste B no le dejaría salir. Y tampoco hay forma de hacer salir directamente la anilla del poste B ya que se lo impedirían el poste A y su anilla. Por eso decimos que las anillas 2ª y 5ª (unidas a los postes B y E) están dentro.
Cada combinación de anillas con sus posiciones dentro o fuera se suele indicar mediante un código binario (introducido en 1872 por Louis Gros en “Théorie du Baguenodier”). En esta codificación se indican con 1 las anillas que están dentro y con 0 las que están fuera. De esta forma la disposición del dibujo anterior se representa con el código 10010. (Observa que en ese número siempre se pone a la derecha el dígito que corresponde al estado de la anilla que no rodea a ningún poste y que decimos que es la primera).
Usando el dibujo que hemos puesto anteriormente (posición 10010) veamos los movimientos que podemos hacer. Habrá que hacer un pequeño esfuerzo imaginativo y de visualización espacial:
a) De la posición 10010 podemos pasar a 10011. Pasando la anilla A de abajo a arriba a través del el interior del bastidor (con un pequeño giro) y a continuación movemos el bastidor a la izquierda para conseguir pasar su extremo derecho a través de la anilla A. Así la anilla “abraza” el bastidor y su poste lo atraviesa, de modo que ahora la consideramos dentro.
b) De la posición 10010 podemos pasar a 10110. Procediendo de forma similar a lo descrito anteriormente con la anilla A, pero ahora aplicado a la anilla C.
Esos dos movimientos descritos serían para introducir las anillas respectivas. Sacar cualquiera de esas anillas sería hacer lo mismo pero en orden inverso. Pero no todas las anillas pueden ponerse o sacarse en cualquier momento. Entonces, ¿Cómo sabemos si una anilla puede ponerse o quitarse?
El movimiento descrito en el apartado a) anterior siempre se podrá hacer si la primera anilla (A) está fuera (Y siempre se podrá deshacer si está dentro). Es decir, siempre podemos cambiar el estado de la primera anilla.
Y la otra anilla que casi siempre podremos cambiar de estado es la que se encuentre justo a la izquierda de la primera que esté dentro. Es decir, empezando por la derecha, nos fijaremos en la primera que encontremos dentro (con 1 en nuestro código) y tendremos que la que esté inmediatamente a su izquierda podrá cambiarse de estado.
Si usamos la posición que hemos puesto de ejemplo (10010) y nos decantamos por poner la primera anilla, llegaremos a la posición 10011 (como hemos descrito en a)). Desde esta posición, y si descartamos la opción de volver atrás, pasaremos a la posición 10001 y de aquí llegamos a 10000. En esta última configuración nos encontramos con que no nos queda más remedio que deshacer el camino andado y volver a poner la primera anilla ya que no hay ninguna anilla a la izquierda de la quinta para poder alterar su estado. La posición 10000 (en el juego con 5 anillas) se dice que es la posición de máximo esfuerzo o extrema. Y en el camino “lineal” que nos proporciona el juego es el extremo más alejado de la solución (que sería 00000).
El juego clásico se suele presentar inicialmente en la posición que tiene todas las anillas dentro (11111 en la versión de 5 anillas de nuestro ejemplo). Aunque también hay versiones (sobre todo las que se presentan en forma de escalera o de marco cuadrado) en las que se empieza el juego en la posición de máximo esfuerzo descrita (10000 si es de 5 anillas).
Para que las personas que no han manipulado el juego puedan familiarizarse con su mecanismo dejo a continuación un enlace para jugar de forma interactiva. El inconveniente es que el mango está justo al revés de lo que yo he descrito hasta ahora en esta página. (Lo de poner el mango a la izquierda es conveniente por la transcripción a código binario introducido por Gros para este puzzle).
Código Gray
El código que usamos para representar los estados del puzzle es binario ya que sólo usa ceros y unos pero no se corresponde con el orden de numeración binaria normal sino con el conocido como código Gray Binario. Este código se caracteriza porque de un código al siguiente sólo se produce un cambio de un dígito (como ocurre con el juego, que sólo cambia una anilla). Esta característica del código fue la que llevó a su uso en la electrónica y para la conversión de analógico-digital hasta nuestros días. Se le conoce por ese nombre por Frank Gray que lo patentó en 1947 aunque ya se fue usado por Baudot en 1870 para el telégrafo.
Podemos crear montones de códigos Gray binarios, pero el que aquí usamos en la representación y análisis de este puzzle es el que se suele llamar código Gray Reflejado (De hecho en la mayor parte de sitios a este código lo llaman simplemente código Gray).
Para desarrollar este código podemos empezar con un solo dígito y construir hasta la cantidad de dígitos que queramos del siguiente modo: Para un dígito el código Gray coincide con la numeración binaria usual:
0
1
Y para continuar añadiríamos otro dígito, que sería 0 a la izquierda para los dos números que ya tenemos escritos y 1 para los dos siguientes, pero esos dos dígitos tendrían en la posición de la derecha los valores “reflejados” de 0, 1 escritos anteriormente: (voy subrayando la posición en la que debemos "reflejar" los dígitos)
00
01
11
10
Para seguir generando el código Gray añadimos otro dígito a la izquierda. Que igual que antes será 0 para esos 4 que ya tenemos y 1 a la izquierda para los “reflejados” de esos 4 códigos:
000
001
011
010
110
111
101
100
Y así sucesivamente podemos crear el código Gray binario reflejado con el número de dígitos que queramos.
Con cinco dígitos queda:
|
00000 |
01100 |
11000 |
10100 |
|
00001 |
01101 |
11001 |
10101 |
|
00011 |
01111 |
11011 |
10111 |
|
00010 |
01110 |
11010 |
10110 |
|
00110 |
01010 |
11110 |
10010 |
|
00111 |
01011 |
11111 |
10011 |
|
00101 |
01001 |
11101 |
10001 |
|
00100 |
01000 |
11100 |
10000 |
El código Gray Binario reflejado de cinco dígitos tiene 25 =32 elementos diferentes, igual que le pasa al código binario natural, pero en otro orden. De hecho ahora después veremos cómo pasar de un código al otro.
En cuanto a nuestros Aros Chinos: La solución del juego corresponde al código 00000 y la típica posición inicial es 11111, aunque a veces también se presentan en la posición extrema 10000. Si queremos resolver el juego con 5 anillas sólo hay que seguir el orden indicado en el código Gray de arriba hacia la solución. Y para volver a poner las anillas en su lugar recorrer el código en orden contrario. Aunque al cogerle el punto al juego nos puede pasar al revés (al menos me pasa a mí), es decir, que para escribir el código Gray imagino las anilla subiendo y bajando y así me dictan el código.
Si nos fijamos en una posición concreta del juego representada en forma de código Gray (o de Gros) y queremos saber cuántos pasos necesitamos para resolverla (llegar a todo ceros), tendremos que contar los pasos en ese código. Y si pudiéramos pasar de Gray a binario natural, después sería solo cuestión de expresar el número binario en decimal.
En internet podemos encontrar varios métodos para pasar de Gray a binario (y también al revés). Incluso hay “calculadoras” para hacerlo. Pero el proceso es relativamente sencillo si usamos la suma módulo 2 o Suma del Nim: 1+1=0 0+0=0 0+1=1 1+0=1
-
Para pasar de Gray a Binario usaremos de ejemplo
el código Gray 01101:
Lo leemos de izquierda a derecha. El primer dígito se conserva siempre igual al pasarlo a binario (0…). Para el siguiente sumamos (módulo 2) el número obtenido de esa primera posición (0) con el siguiente del código gray (1) y obtenemos el segundo dígito por la izquierda en binario (ya tenemos 01…). Este proceso se repite tomando el dígito que acabamos de obtener (1) y sumando con el siguiente del código Gray (1) para obtener otro dígito en binario (010…). Repitiendo dos veces más el proceso llegamos a 01001 (que es 9 en notación decimal).
-
Para pasar de Binario a Gray el proceso es
parecido. Usaremos de ejemplo el número binario obtenido anteriormente 01001:
Leemos de izquierda a derecha. El primer dígito se copia igual (0…). Para el siguiente se suman las dos primeras cifras del binario 0+1 (01…). Para el siguiente se suman la segunda cifra y la tercera (por la izquierda) del binario 1+0 (011…). Y así sucesivamente se llega al código gray 01101.
Y puesto que en binario siempre podemos considerar que a la izquierda tenemos un cero, ambos procesos se podrían resumir en el siguiente gráfico, donde las flechas indican qué sumar en módulo 2 y dónde colocar el resultado:
De esta forma ya podemos saber cuántos pasos hay desde cualquier posición de los Aros chinos a su solución (con cualquier número de anillas). Por ejemplo, el de 5 anillas sería empezar con un código Gray 11111 que equivale a 10101 en binario y si a su vez ese número lo pasamos a decimal sería 16+4+1=21 que es el número de movimientos que se necesitan.
Si tenemos 6 aros sería 111111 que en binario es 101010 y en decimal 32+8+2=42.
Y si empezamos en la posición extrema por ejemplo con 7 aros (1000000) nos da el binario 1111111 que en decimal es el 26+25+24+23+22+21+1=27-1=127
No es necesario manejar el puzzle demasiado tiempo para observar que es una buena estrategia ir imaginando las anillas por parejas (empezando a hacer esas parejas por la izquierda según el código Gray). Es lógico ya que para poner o quitar una anilla antes tiene que estar la de su derecha puesta y que no tengamos mas a la derecha ninguna otra anilla puesta.
Contando el número de pasos
En 1872 Louis Gros encontró las fórmulas que nos permiten saber cuántos pasos son necesarios para resolver los aros chinos con cualquier número de anillas. Para encontrar estas fórmulas se usan argumentos recursivos, pero lo más sencillo es ver cómo se pasa el código Gray a binario y usar la suma de los primeros elementos de una serie geométrica. Así se llega a que:
Si n es par el número de pasos es de
Y si n es impar se necesitan
.
Estas dos fórmulas se pueden unificar usando la función “parte entera” (representada con corchetes):
Otro camino para encontrar la fórmula que
nos diga el número de pasos que son necesarios sin tener que usar la función
“parte entera” lo estudió de forma independiente en 1769 Georg Christoph (en
paralelo a Yoriyuki Arima).
Yoriyuki Arima encontró y usó la fórmula ln+ ln-1=2n – 1 donde ln representa el número de pasos para poner (o
quitar) n anillas. El sentido de esa fórmula se ve claro si nos imaginamos la
solución del puzzle en su posición extrema (100...00) que requiere poner las
n-1 anillas de la derecha (llegando a 111…11) y luego quitar las n anillas para
resolverlo usando 2n – 1 pasos (ya que recorremos todos los números binarios de n dígitos).
Y Georg Christoph usó la recurrencia ln+1= ln + 2 ln – 1 + 1 , esta fórmula refleja que para resolver el puzzle con n+1 aros (ln+1) hay que quitar las n-1 primeras anillas (ln–1) y dejar puestas las dos de la izquierda, luego quitar la última (+1), luego volver a poner las n-1 primeras (ln–1) y por último quitar las n anillas (ln). Según algunas de las fuentes que he consultado también llegó a la expresión que he mencionado en el párrafo anterior.
Y usando las fórmulas recurrentes anteriores podemos encontrar una expresión en función de n que evita tener que usar la función parte entera:
Solución Rápida
Los aros chinos tienen también la particularidad de que si las dos primera anillas están ambas en la misma posición, estas pueden ponerse o quitarse ambas a la vez en lo que podríamos considerar como un solo movimiento. De este modo el número de pasos para llegar a la solución si permitimos este atajo es menor que el que ya hemos detallado usando el código Gray.
Esta forma de resolver el puzzle ya era comentado por Cardano e 1550. La fórmula recurrentes que se pueden usar para contar los pasos necesarios en este caso son las mismas que para el camino largo, sólo difieren en lo que podríamos llamar las condiciones iniciales. Las fórmulas que podemos encontrar para el número de pasos dependiendo de la paridad de n son:
Si n es par el número de pasos es de
Y si n es impar se necesitan
Y lamentablemente la fórmula para eliminar esa diferencia en la paridad también es algo más compleja como sucedía para el camino largo:
No hay comentarios:
Publicar un comentario