El juego de taquín, a propósito de Galois

Piste bleue Le 4 novembre 2011  - Ecrit par  Michel Coste
Le 18 mai 2020  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Le jeu de taquin, du côté de chez Galois Voir les commentaires
Lire l'article en  

Este artículo se publicó simultáneamente en el sitio del Bicentenario del nacimiento de Evariste Galois->http://www.galois.ihp.fr/ressources/] (IHP y SMF). Agradecemos en especial al autor por haber permitido esta colaboración.

El juego de taquín y el problema de Sam Loyd

Tal vez usted conozca el juego de taquín. Se compone de un tablero que contiene quince placas enumeradas de 1 a 15, y que deja un espacio en el cual se puede hacer deslizar una placa vecina.

PNG - 13.5 ko
PNG - 8.3 ko

Sam Loyd propuso hace más de un siglo un problema que ha hecho correr bastante tinta : ¿se puede pasar de la posición inicial a la posición en que las casillas 14 y 15 se intercambian mediante una secuencia de movimientos autorizados del taquín ? (está formalmente prohibido el uso del mango de una cucharilla para desmontar el taquín)

PNG - 13.7 ko
PNG - 2.5 ko
PNG - 13.6 ko

Para responder al pequeño problema de Sam Loyd, vamos a estudiar cómo las configuraciones del taquín cambian con los movimientos autorizados. Será más fácil trabajar con números dispuestos en una fila que ordenados en el tablero. A una posición del taquín asociaremos la lista de números que se encuentra recorriendo las casillas a lo largo del camino indicado en verde abajo. No se tomará en cuenta la casilla vacía. El camino se parece a una fila de espera ante una ventanilla de estación, entre barreras que zigzaguean, ¿verdad ?

PNG - 7.3 ko

De esta forma se obtiene un ordenamiento de los números de 1 a 15. Por ejemplo, el ordenamiento de la configuración de inicio del taquín es

4 3 2 1 5 6 7 8 12 11 10 9 13 14 15

El ordenamiento de los números de 1 a 15 no determina completamente la configuración del taquín, ya que no entrega información acerca de la posición de la casilla vacía. Sin embargo, como uno puede mover la casilla vacía a lo largo del camino mediante los movimientos autorizados del taquín, esto no importa : si se puede llegar a una de las configuraciones que da un cierto orden, entonces se podrá también llegar a todas las configuraciones que dan el mismo orden.

Número de intercambios

Vamos a medir el ’’desorden’’ de un orden R dado a los números de 1 a 15 (o de 1 a un natural cualquiera) en relación al orden creciente. Para esto, diremos que una pareja de números presenta un intercambio en el orden R si el mayor de los dos números aparece antes que el más pequeño en R. Por ejemplo, en el ordenamiento siguiente de los números de 1 a 9

9 2 5 4 1 6 8 3 7

la pareja 3,5 presenta un intercambio, pero la pareja 4,6 no. ¿Cuántos intercambios hay en todo el ordenamiento de arriba ? No es obvio cómo contar sin equivocarse. He aquí hay un método. Se comienza por las parejas con 1 : el número 1 -que es el más pequeño- presenta un intercambio con todos los números que está ordenados antes que él. Eso da cuatro intercambios (con 9, 2, 5 y 4). Borremos 1.

9 2 5 4 $\ $ 6 8 3 7

Ahora 2 es el más pequeño de los números restantes y presenta un intercambio con todos los números ordenados antes que él. Eso significa solo un intercambio (con 9). ¿Ves cómo continuar ? Se borra 2 y se cuenta los números antes de 3, se borra 3 y se cuenta los números antes de 4, etc. (para facilitar el recuento, los ’’números antes’’ están subrayados en la tabla de abajo).

9 $\ $ 5 4 $\ $ 6 8 3 7
9 $\ $ 5 4 $\ $ 6 8 $\ $ 7
9 $\ $ 5 $\ $ $\ $ 6 8 $\ $ 7
9 $\ $ $\ $ $\ $ $\ $ 6 8 $\ $ 7
9 $\ $ $\ $ $\ $ $\ $ $\ $ 8 $\ $ 7
9 $\ $ $\ $ $\ $ $\ $ $\ $ 8 $\ $ $\ $

En total, hay 17 intercambios. Armados con el método que acabamos de describir, podemos encontrar sin error el número de intercambios de orden de 1 a 15 asociado a la configuración de inicio del taquín : 12 intercambios (¿los encontraste ?). Nos hemos dado mucho trabajo para calcular el número de intercambios, pero, en realidad, lo único que va a interesarnos a continuación es saber si ese numero de intercambios es par o impar.

Saltos de cordero

Si partimos de un orden de los números de 1 a 15, ¿mediante qué operaciones se puede colocar los números en el orden creciente ? Pues bien, basta con utilizar los ’’saltos de cordero’’ : un salto del cordero consiste en hacer saltar un número que no está en primer lugar del ordenamiento por encima del que le precede. Por ejemplo, en una situación donde solo están los números de 1 a 4 :

PNG - 82.3 ko

Se aprecia fácilmente una manera de volver a colocar los números en el orden creciente utilizando los saltos de cordero : primero se debe llevar el 1 al primer lugar -si es que ya no está ahí- mediante saltos de cordero, luego llevar el 2 al segundo lugar, etc. En el ejemplo de arriba, el cordero que salta por encima del que le precede está indicado en rojo :

2 4 1 3
2 1 4 3
1 2 4 3
1 2 3 4

Los lectores atentos sin duda habrán notado que, mediante este procedimiento, el número de saltos de cordero utilizados para volver a colocar los números en el orden creciente (tres saltos de cordero, por ejemplo) es exactamente igual al número de intercambios del orden de inicio. Pero uno podría imaginar otras maneras de proceder, por ejemplo :

2 4 1 3
2 4 3 1
2 3 4 1
2 3 1 4
2 1 3 4
1 2 3 4

Esta vez se ha procedido en cinco saltos de cordero. ¿Se podría haber hecho en cuatro saltos de cordero ? Para responder a esta pregunta, examinemos cómo varía el número de intercambios del orden con el salto de cordero. Ya que un salto de cordero solo intercambia los lugares de dos números vecinos, disminuye en uno el número de intercambios si esos dos números estaban dispuestos en mal orden al inicio, y aumenta en uno si estaban dispuestos en el orden correcto. En ambos casos, el número de intercambios cambió de paridad : si era par se volvió impar, y viceversa. Por lo tanto, para pasar del ordenamiento 2, 4, 1, 3 de inicio (donde el número de intercambios es tres, un número impar) al ordenamiento en orden creciente (es decir el ordenamiento en el cual el número de intercambios es cero, un número par) necesariamente se debe realizar un número impar de saltos de cordero. En particular, no se puede hacer en cuatro saltos de cordero. Retengamos bien lo que nos sirvió :

Cada salto de cordero cambia la paridad del número de intercambios.

La solución del problema de Sam Loyd

Un movimiento autorizado del juego de taquín modifica el ordenamiento de los números de 1 a 15 asociado a la configuración cuando el desplazamiento de la casilla vacía no se hace a lo largo del camino verde descrito más arriba. Por ejemplo ¿qué sucede si uno efectúa los movimientos indicados abajo ?

PNG - 8.2 ko
PNG - 8.3 ko

El movimiento de la izquierda hace retroceder el número sobre la casilla que salta dos lugares en la fila de espera. Esto se puede hacer con dos saltos de cordero en el ordenamiento de los números. El movimiento de la derecha hace avanzar el número sobre la casilla que se mueve cuatro lugares en la fila. Esto se puede hacer con cuatro saltos de cordero. En ambos casos el número de saltos de cordero es par y por lo tanto la paridad del número de intercambios no varía. Fácilmente uno se convence de que sucede lo mismo para todos los movimientos autorizados del taquín : si cambian el ordenamiento, es haciendo avanzar o retroceder un número ya sea dos, cuatro o seis lugares en la lista.

Un movimiento autorizado del taquín no cambia la paridad del número de intercambios.

Volvamos ahora al problema de Sam Loyd. Se puede pasar del orden de los números asociado a la configuración de inicio a aquella donde el 14 y 15 son intercambiados mediante un solo salto de cordero. Por lo tanto, las paridades de los números de intercambios de los dos órdenes son diferentes. Esto muestra que no se puede pasar de la configuración de inicio a aquella donde 14 y 15 están intercambiados mediante una secuencia de movimientos autorizados por el taquín, ya que estos conservan la paridad del número de intercambios.

Es imposible llegar a la configuración planteada por Sam Loyd utilizando solo los movimientos autorizados del taquín.

¿Y después ?

La resolución del problema de Sam Loyd no agota las preguntas que uno puede plantearse a propósito del juego de taquín. Una pregunta que surge naturalmente es la siguiente : hemos visto que una configuración que puede obtenerse mediante los movimientos autorizados del taquín verifica obigatoriamente la invarianza de la paridad del número de intercambios (del ’’signo’’, siguiendo la terminología matemática). Pero en el otro sentido, una configuración que verifica la invarianza del signo, ¿puede siempre obtenerse mediante los movimientos autorizados del taquín ? Se puede hallar la respuesta (¡positiva !) a esta pregunta, redactada en un lenguaje matemático bastante sofisticado, en este texto.

Otra pregunta, sin duda más fácil que la anterior : ¿qué sucede si se reemplaza el tablero de 4×4 casillas por un tablero de 1811×2011 casillas, con (1811×2011) – 1 = 3641920 placas numeradas ? El problema de Sam Loyd (el cambio de las placas numeradas 3641919 y 3641920), ¿podría tener una solución para ese gigantesco taquín donde se tiene más libertad de movimiento ?

Usted también puede jugar de manera interactiva con un taquín no estándar propuesto en el sitio dedicado al bicentenario del nacimiento de Évariste Galois. Se analiza de la misma manera que el taquín presentado en este artículo : poco importa en el fondo lo que está escrito sobre las placas, desde el momento en que se pueda diferenciarlas.

Se puede leer muchas cosas interesantes en torno al taquín en el capítulo del libro de Édouard Lucas (Récréations mathématiques, vol. 1, Gauthier-Villars 1882 — nuevo tiraje, Blanchard 1960) dedicado a este juego. Acá abajo usted puede comprobar que Lucas considera incluso ¡’’taquines en bifurcaciones y garage’’ !

PNG - 1.1 Mo

¿Por qué Galois ?

¿Cuál es la relación entre Évariste Galois y el taquín ? En realidad, la herramienta que hemos utilizado -a saber, los ordenamientos de los números de 1 a 15- se llama en términos más científicos las permutaciones del conjunto {1,2,…,15}. Las permutaciones ocupan un lugar central en la obra de Galois : es al estudiar las permutaciones del conjunto de soluciones de una ecuación que él pudo establecer que las soluciones de una ecuación de grado superior o igual a 5 en general no pueden encontrarse utilizando radicales. Algunas pocas palabras de explicación : en el liceo se enseña que las dos soluciones de la ecuación de segundo grado $ax^2+ bx +c=0$ están dadas por la fórmula
\[\frac{-b\pm \sqrt{b^2-4ac}}{2a}\;.\]
Para una ecuación de grado 3 (donde la incógnita $x$ aparece elevada al cubo $x^3$) se dispone también de las fórmulas de Cardan, que entregan las tres soluciones por medio de operaciones aritméticas, de extracción de raíces cuadradas $\sqrt{\ }$ y de raíces cúbicas $\sqrt[3]{\ }$ (de manera general, se llama ’’radicales’’ a las raíces $n$-ésimas $\sqrt[n]{\ }$).

Puedes ver enfrente una página extraída de una memoria de Galois. Ahí considera los grupos de permutaciones de cuatro letras a, b, c, d que representan las cuatro soluciones de una ecuación de grado cuatro. Él explica cómo la resolución de una tal ecuación mediante radicales corresponde a un encajonamiento de tales grupos de permutaciones cada vez más pequeños. En general, la resolubilidad de una ecuación por radicales corresponde a la posibilidad de realizar encajonamientos de grupos de permutaciones que tengan propiedades adecuadas. Para más informaciones acerca de los grupos, puedes consultar el artículo de Christine Huyghe en este sitio.

Los saltos de cordero que nos fueron tan útiles son ejemplos de transposiciones (las transposiciones son permutaciones que no hacen más que cambiar dos elementos del conjunto). Lo que hemos mostrado aprovechando la ocasión, a saber, que se puede volver a colocar en orden creciente los números sin importar el orden utilizando solo saltos de cordero, se enuncia como el teorema matemático siguiente : las transposiciones de dos números sucesivos generan el grupo de permutaciones de {1,2,…, {n} }.

El argumento clave para demostrar la imposibilidad del problema de Sam Lloyd ha sido la invarianza de la paridad del número de intercambios. La paridad del número de intercambios es lo que los matemáticos llaman el signo de una permutación. Lo que nosotros hemos visto utilizando los saltos de cordero es una demostración del teorema que dice que el signo es el único homomorfismo no trivial del grupo de las permutaciones de {1,2,…, {n} } en el grupo Z/2Z. Es más impresionante dicho así, ¿cierto ?

Post-scriptum :

El autor agradece su atenta relectura a los relectores cuyo seudónimo es el siguiente : Muriel Salvatori, Roland Bacher, Bruno Duchesne, Pierre D. y Simon IOSTI.
La redacción agradece a Xavier Caruso del sitio Bicentenaire de la naissance d’Evariste Galois por su ayuda en esta colaboración.

Article original édité par Serge Cantat

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «El juego de taquín, a propósito de Galois» — Images des Mathématiques, CNRS, 2020

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?