Juego de Baguenaudier

El baguenaudier o baguenodier (etimológicamente "ring knot"; en inglés chino Rings , Cardan's Suspension , Cardano's Rings , Devil's needle o rompecabezas de cinco pilares ) es un rompecabezas mecánico compuesto por una lanzadera móvil que forma un bucle cerrado (posiblemente flexible) y anillos rígidos. (móvil si la lanzadera es rígida) cada uno retenido por una varilla unida al mismo soporte.

Este juego ha sido estudiado en sus obras por John Wallis y Jérôme Cardan .

El juego podría ser de origen chino.

Solución matemática

Édouard Lucas , el inventor de las torres de Hanoi , propuso una solución basada en el sistema binario y el código de Gray que se formula como su rompecabezas. El número mínimo de desplazamientos para resolver un problema de anillo se da a continuación (referenciado A000975 en la OEIS ): $no$

a (n) = \ lceil \ tfrac {2 ^ {n + 1} -2} {3} \ rceil = \ begin {cases} \ frac {2 ^ {n + 1} -2} {3}, & \ text {cuando} n \ text {es par,} \\ \ frac {2 ^ {n + 1} -1} {3}, & \ text {cuando} n \ text {es impar.} \ end {cases}

donde está la parte total sobrante (techo) de . $\ lceil x \ rceil$ $X$

Versión algorítmica

Consideremos una representación binaria del juego. Resolver el juego significa poner todas las casillas en 1 (o viceversa, ponerlas todas en 0).

Con un baguenaudier físico, "llenar" o "vaciar" las cajas consiste en pasar (en el orden correcto) un aro principal o un cordón dentro o fuera de uno de los pequeños anillos del juego para soltar el cordón o el aro principal de todos los anillos pequeños, o bien aprisionar el cordón o el aro por todos los anillos pequeños: las "cajas" representan el estado de cada uno de los anillos pequeños (es decir, si el aro grande o el cordón pasa o no por cada uno de los anillos). anillo pequeño).

Sin embargo, jugar con el cable flexible requiere un manejo más fácil para cambiar de un estado a otro; jugar con el aro inflexible requiere más destreza para pasar los anillos pequeños entre sí, incluso si el aro pasa o no por su centro (que entonces son de diferentes diámetros o deformables elásticamente, o luego inflexibles pero de forma ovoidal, que luego requiere para controlar su rotación de forma precisa, especialmente si los óvalos están muy ligeramente aplanados, con solo el aplanamiento necesario para poder pasar uno de los pequeños anillos a otro).

En la versión china del baguenaudier, la dificultad de manejo aumenta por el hecho de que cada uno de los anillos pequeños es inflexible y del mismo tamaño (como es el aro), pero los anillos pequeños están sujetos por un gancho (que puede girar). libremente) en el extremo de una varilla corta inflexible, manteniéndose las varillas (todas de la misma longitud) paralelas con espaciamiento regular en un soporte inflexible, pero pudiendo deslizarse longitudinalmente a través de este soporte: en lugar de orientar los anillos, pueden ser avanzar o retroceder deslizando en el soporte la varilla donde se enlaza cada anilla para luego poder realizar las rotaciones de las anillas en la posición del anzuelo. Esta disposición es inquietante para el experimentador del juego que no percibe bien cómo el problema es en realidad más simple de lo que parece, pero requiere una gran destreza para resolverlo porque es necesario orientar adecuadamente los anillos (que giran muy libremente alrededor su gancho) y ajustar el deslizamiento de las varillas (que también es gratis): este problema no se puede solucionar si las varillas no son horizontales (para que no se deslicen por sí mismas en el soporte debido a la gravedad, que también tiene el efecto de reorientando cada uno de los anillos pero no de la forma deseada por el operador).

Pero para un experimentador que conoce la técnica de la manipulación, la versión inflexible del baguenaudier permite una manipulación mucho más rápida (al menos un cambio o "golpe" por segundo) que con una lanzadera flexible (donde cada cambio puede tardar varios segundos mientras se toma. Tenga cuidado de mantener los bucles flexibles de la lanzadera para que permanezcan en cada anillo, pero la elasticidad de la flexión de la lanzadera puede hacer que cambie de lugar si el manipulador no retiene los bucles extremos mientras mantiene suficiente tensión longitudinal en la lanzadera. .este, pero a menudo este volante es más largo de lo necesario y no permanece tenso, por lo que uno de los bucles puede escapar fácilmente del anillo donde el manipulador lo había colocado).

Pero algorítmicamente los problemas a resolver en estos baguenaudiers físicos (de los cuales hay muchas variantes en el mundo, desde hace varios milenios para algunos) son equivalentes al problema matemático con "cajas" binarias (que no requiere ninguna destreza de manipulación pero solo el pensamiento lógico).

Reglas

Siempre puede invertir (pasar de 1 a 0 o viceversa) la casilla 1.
No podemos revertir ("vacío" o "preguntar") cuadro , que: j{\ Displaystyle j} $j$ j∈[2,no]{\ Displaystyle j \ en [2, n]} ${\ Displaystyle j \ en [2, n]}$
- si la celda está en 1 y todas las celdas anteriores están en 0, o ${\ Displaystyle j-1}$
- si la celda está en 0 y todas las celdas anteriores están en 1. ${\ Displaystyle j-1}$

Estas reglas son completamente simétricas, obtenemos una solución en sentido contrario si invertimos los valores 1 y 0 en todas las casillas simultáneamente. Esto también da una solución equivalente al problema contrario (liberar el cordón o el aro de los anillos pequeños, o lograr pasarlo por todos los anillos pequeños).

De la misma manera, el problema puramente binario utiliza una numeración (un orden) preestablecida de las casillas, pero en general arbitraria (todos pueden implicar permutar las casillas). El juego físico, en cambio, impone un orden, impuesto por su construcción, pero este orden no añade ninguna dificultad a la resolución algorítmica del problema que proporciona una solución cualquiera que sea este orden impuesto al inicio.

Solución para $n = 4$

Se necesitan un mínimo de 10 movimientos (y menos de 10 segundos) para resolver el baguenaudier . Cada 2 movimientos, es la caja 1 la que se invierte, cada 4 movimientos es la caja 2 la que se invierte, las cajas en la última mitad se invierten cada una solo una vez en movimientos separados (con 4 golpes de diferencia entre estos golpes). Son posibles varias soluciones (de forma combinatoria debido a la simetría del problema y al orden inicial arbitrario de las casillas), por lo tanto hay soluciones mínimas en 10 movimientos, de los cuales aquí hay uno (que también representa una solución del problema inverso , leyéndolo de izquierda a derecha o de derecha a izquierda, o alternativamente permutando la interpretación de los estados 1 o 0 de cada casilla; si realizamos estos dos cambios de interpretación simultáneamente, obtenemos también una segunda solución del mismo problema inicial porque esto equivale simplemente a invertir el orden de las cajas y por lo tanto da otra de las 24 permutaciones posibles). : $n = 4$ ${\ Displaystyle n! = 24}$

Caso 1:	1		1	⬌	0		0	⬌	1		1	⬌	0		0	⬌	1		1	⬌
Caso 2:	1	⬌	0		0		0		0	⬌	1		1		1		1	⬌	0
Caso 3:	1		1		1		1		1		1		1	⬌	0		0		0
Recuadro 4:	1		1		1	⬌	0		0		0		0		0		0		0

Los baguenaudiers se construyen tradicionalmente con un número impar de anillos: los modelos más comunes con 5 anillos requieren 21 golpes (y por lo tanto pueden abrirse y cerrarse fácilmente en menos de 20 segundos con componentes inflexibles). Existen modelos con 7 anillos, que requieren un mínimo de 85 golpes y por lo tanto un poco más de un minuto para abrirlos o cerrarlos en un mínimo de golpes. Un modelo rígido de 9 anillos requiere al menos 341 golpes y, por lo tanto, casi 6 minutos de manejo continuo (al menos un golpe por segundo) para abrirlo o cerrarlo completamente sin error.

Algoritmo

borrar (n) hace que las n casillas del baguenaudier vayan de 1 a 0, rellenar (n) hace que las n casillas del baguenaudier vayan de 0 a 1. poner (i) hace que la casilla i sea igual a 1, quitar (i) hace que el caso i sea igual a 0.

def remplir(n) : if n == 1 : poser(1) elif n > 1 : remplir(n-1) vider(n-2) poser(n) remplir(n-2) def vider(n) : if n == 1 : enlever(1) elif n > 1 : vider(n-2) enlever(n) remplir(n-2) vider(n-1)

seguridad

El baguenaudier binaria fue utilizado una vez como un elemental pseudo bloqueo de los campesinos franceses. Sin embargo, esto no puede constituir una seguridad real, porque cualquiera que sea el estado del objeto (excepto cuando está totalmente cerrado o totalmente abierto), solo se puede manipular en dos direcciones: la gráfica completa del juego se reduce a un solo segmento que une el estado de apertura total y el de cierre total. Si hemos entendido cómo manipular el objeto, y aunque no sepamos en qué dirección empezar, podemos elegir uno de los dos y hacer las manipulaciones sin volver jamás, y acabaremos o bien en la situación en la que el el objeto está completamente abierto o donde está completamente cerrado; si esta no es la situación que se quería obtener, basta con reanudar las operaciones en sentido contrario para obtener el estado final deseado. La única seguridad que se obtiene (ya que estamos seguros de encontrar una solución fácilmente) es la del tiempo necesario para la manipulación para abrir dicha cerradura, esta vez dependiendo únicamente del número de timbres.

Existen otros juegos más complejos basados en el entrelazado, cuya resolución algorítmica obedece a una lógica no binaria: entonces es mucho más complicado explorar las diferentes posibilidades posibles en cada movimiento. Por ejemplo, en lugar de tener una sola lanzadera, todo lo que tienes que hacer es agregar al menos una segunda que también se entrelazará con los anillos y con la otra lanzadera. En cada paso, por lo tanto, debemos determinar qué lanzadera manejar (podemos llamar a este juego una "bolsa de nudos", se encuentra comúnmente en un problema conocido de almacenamiento de cables, que es particularmente difícil de desenredar una vez que están entrelazados en un contenedor manipulado sin precaución) y el juego siempre ofrece posibilidades inexploradas o no fáciles de determinar como ya exploradas (porque el entrelazado enmascara una parte de sus estados internos a los que el manipulador no tiene acceso o al que provocó el cierre sin saberlo). Sin embargo, existen juegos de entrelazado de lógica no binaria, que utilizan partes cuyos estados no están ocultos al usuario, y siempre ofreciendo más de dos movimientos posibles en cada paso: para resolverlos, el usuario debe apelar en su memoria para recordar las combinaciones ya. explorado, pero su número explota rápidamente de manera combinatoria o exponencial, este juego luego se vuelve muy difícil o incluso imposible de resolver por un humano, que no sabe entonces si está en el camino correcto hacia la solución deseada. Por otro lado, si el usuario conoce o tiene la combinación (la llave) que conduce a la apertura, puede pasar rápidamente por un número predefinido y limitado de pasos y encontrar la solución (abrir o cerrar la cerradura) fácilmente sin perder demasiado. time. time (que no es el caso del clásico baguenaudier).

El gráfico de tales juegos no forma una línea, sino árboles orientados con muchas ramas, posiblemente con bucles internos potencialmente infinitos (que pueden ser indetectables si el juego oculta deliberadamente parte de sus estados internos al jugador en una caja negra e interactúa solo con el jugador). como un "oráculo" que da respuestas deliberadamente limitadas). Estos conjuntos pueden luego utilizarse para constituir verdaderas herramientas de seguridad (y por lo tanto utilizables como " cerraduras ": existen precisamente aquellos que se basan en complejos ensamblajes internos de ruedas dentadas, resortes de retorno y muescas de bloqueo que reemplazan la simple lanzadera, donde cualquier error de manejo obliga a que las operaciones se reanuden desde el principio en un estado totalmente cerrado, siendo bloqueado el retroceso por parte del equipo con el fin de ralentizar considerablemente la exploración sistemática de las posibilidades; una dificultad adicional es que incluso el usuario, que no conoce la correcta secuencia de apertura, no sabe cuándo el equipo vuelve automáticamente a una configuración de cierre total, porque los mismos movimientos mecánicos internos forman parte de la secuencia de apertura correcta).

La versión modernizada (y modelada matemáticamente) de estos juegos complejos consiste en los algoritmos de cifrado utilizados por la informática (por ejemplo, basados en la descomposición de números enteros en factores primos) y basados en combinatoria aritmética no binaria (donde en cada paso hay son más de dos movimientos posibles y donde no es fácil determinar cuál conduce a la solución deseada sin tener que explorar todas las avenidas posibles, con muchos retrocesos o reanudaciones desde el principio en caso de falla).

Bibliografía

Luc-Agathon-Louis Gros , Teoría del baguenodier por un escribiente de un notario de Lyon , Lyon, Aimé Vingtrinier ,1872( leer en línea )
Édouard Lucas , Recreaciones matemáticas , vol. 1, París, Gauthier-Villars ,1882, " Séptima recreación: El juego baguenaudier ", p. 161–186
Auguste Héraud , Juegos y recreaciones científicas: aplicaciones fáciles de las matemáticas, la física, la química y la historia natural , París, Jean-Baptiste Baillière et fils ,1884, cap. XVI (" Juegos matemáticos y juegos de azar: juego de Baguenaudier "), p. 604-609

Referencias

Lucas 1882 , p. 177 [ leer en línea ] .
Héraud 1884 , p. 604 [ leer en línea ] .
Gros 1872 , " Álgebra de Wallis ", p. 8-11.
Gros 1872 , " Sutileza del cardan ", p. 5-8.
(en) David Darling , " Anillos chinos " , Enciclopedia de la ciencia sobre los mundos de David Darling .
(en) Eric W. Weisstein , " Baguenaudier " en MathWorld .