2: Sam Loyd y el Taken

Hace 20 ó 30 años, casi todo mi tiempo libre era devorado por Caissa, la diosa ingrata de los ajedrecistas.
En el templo de los 64 escaques conocí a Samuel Loyd, compositor de problemas endiablados. Sirva este como ejemplo, en el que las blancas deben dar mate en tres movimientos, cosa a primera vista imposible. La solución, por si alguien se rinde, puede verse al final de esta entrada.

Samuel Loyd, también compuso otros puzzles de inspiración matemática, como este, llamado Klondike, que es uno de sus inventos más famosos

cuyas instrucciones dicen así:

Comenzar a partir del corazón que se encuentra en el centro e ir tres pasos en línea recta, en alguna de las ocho direcciones, norte, sur, este u oeste, o en el sesgo, como dicen las señoras, noreste, noroeste, sureste o suroeste. Cuando haya avanzado los tres pasos en línea recta, usted estará parado sobre una baldosa con un número inscrito en ella, que indica la cantidad de pasos a recorrer en su segundo día: avance la cantidad de pasos indicada en una línea recta en cualquiera de las ocho direcciones. Desde este nuevo punto, cuando llegue, debe caminar de nuevo de acuerdo con el número indicado en la nueva baldosa, y continuar después, según indiquen las baldosas a las que vaya usted llegando, hasta que llegue a una baldosa con un número que le permita caminar JUSTO un paso más allá de la frontera. Al llegar a este punto usted habrá salido de los bosques y puede caminar todo lo que quiera ya que habrá resuelto el rompecabezas.

Hasta aquí nada que objetar. Hallar la solución del Klondike, por ejemplo, sólo requiere paciencia franciscana.
Pero, acabando la década de 1870, Samuel Loyd inventa algo esencialmente distinto: el "Juego del 15", o "Juego del Jefe", o "Jeu de Taquin" o a raíz de la pronunciación francesa "Juego del Taken". Este juego no aparece en escena como otros, ocupando en los escaparates el lugar destinado a las novedades. No, nada de eso.
Las cajitas de madera con este aspecto,

cuyas fichas numeradas pueden deslizarse por filas y columnas gracias al hueco que deja la inexistente ficha "16", se ponen a la venta en esta posición,

junto con el anuncio de un premio de mil dólares para quien descubra la secuencia de movimientos que lleva a esta otra posición

Mil dólares de 1880 vienen a ser, haciendo la cuenta a lo bestia y redondeando sin miramientos, dos millones de euros de 2012.

Se desató la locura. No sólo en EEUU. En medio mundo. Los casos más graves se pasaban día y noche dándole vueltas al problema. Había quien se encerraba donde fuese durante el tiempo de trabajo para seguir probando variantes sin que su jefe lo viese (de ahí uno de los nombres del juego). Hubo quien rozó el abismo de la demencia. Hubo quien cayó en él. Hubo quien iba bien en los estudios y dejó de estudiar, absorbido por el Jeu de Taquin. Hubo matrimonios rotos.

En 1882, varias empresas estadounidenses se ponen de acuerdo: "Quien sea sorprendido durante la jornada laboral manipulando la dichosa cajita de las quince fichas, será despedido en el acto". Hay cientos de despidos. En Inglaterra y en Holanda también se dan casos muy graves aunque en territorio europeo la peor parte le toca a Alemania y a Francia. En Alemania se llegan a detener sesiones parlamentarias porque nadie hacía caso al ponente. En Le Monde, un prestigioso columnista opina que el jeu de Taquin es un azote para la humanidad, una maldición peor que el alcohol y el tabaco; no le falta razón: en las plazas de París se reúne gente al borde del suicidio, completamente obsesionada por resolver el enigma.

Ay, ay, ay... Con la de tiempo que he pasado resolviendo problemas ajedrecísticos de Sam Loyd... ¡Aquí se te fue la mano, amigo mío!
En la Oficina de Patentes de San Francisco le pidieron la solución del puzzle, y Sam Loyd en persona dijo ser plenamente consciente de que el problema es insoluble. De hecho, le negaron la patente. Y en el informe consta que se deniega porque "Un acertijo irresoluble carece de utilidad y en consecuencia no puede patentarse".

El problema propuesto, ¿es de hecho imposible? Rotundamente sí. Veamos por qué.

¿Recuerdan las Torres de Hanoi? Se resolvían conservando la paridad del sistema.
La clave, otra vez, es la paridad del sistema formado por todas las fichas.

Tomemos una posición cualquiera de las fichas

y olvidemos que están dentro de un cuadrado, olvidemos que son los elementos de una matriz de 4 filas por 4 columnas; en su lugar, escribámoslos por orden, tal como nos los iríamos encontrando si los recorriésemos con el dedo SIN LEVANTAR EL DEDO y empezando en una esquina CON ficha. Obtendríamos esto:

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

El hueco está en la esquina: sólo puedo bajar el 8 o desplazar a la derecha el 7. En ambos casos, la secuencia numérica permanece inalterada. ¿Sí?
Luego los movimientos hechos cuando el hueco está en una esquina no alteran la secuencia.

¿Y si el hueco no está en la esquina?

Veamos.
Primero: los movimientos laterales. Es obvio que NO ALTERAN la secuencia.
Segundo: los verticales. El descendente pasa el número que estaba segundo a sexto.
El ascendente pasa el número que estaba noveno a séptimo.

De segundo a sexto. Ambas posiciones son PARES.
De novenos a séptimo. Ambas posiciones son IMPARES. ¡Qué buena pista!

Sigamos.

Sea la secuencia 1 2 3 4. Es la secuencia natural, el orden natural de los números naturales.
Imaginemos que cada número es una ficha sólida.
Imaginemos que la ficha 2 salta por encima de la ficha 1. Tendríamos esta nueva secuencia: 2 1 3 4.
En esta secuencia el 1 y el 2 han invertido sus posiciones. Esta secuencia tiene UNA inversión. Supongamos que ahora la ficha 3 salta por encima de la ficha 4. Tendríamos esta nueva secuencia 2 1 4 3. Están invertidas las posiciones de la pareja 1 2 y las posiciones de la pareja 3 4. Esta secuencia tiene DOS inversiones.

La secuencia 2 1 3 4, por tener UNA inversión tiene un número impar de inversiones. En lenguaje matemático estricto: "la secuencia 2 1 3 4 es una permutación IMPAR de la secuencia original 1 2 3 4".

La secuencia 2 1 4 3, por tener DOS inversiones tiene un número par de inversiones. En lenguaje matemático estricto: "la secuencia 2 1 4 3 es una permutación PAR de la secuencia original 1 2 3 4".

Ejercicio: Calcular el número de inversiones de la secuencia
9 2 5 4 1 6 8 3 7
La solución, al final de la entrada.

Seguimos.
Los movimientos legales (ficha 2ª pasa a 6ª, ficha 9ª pasa a 7ª) alteran el número de inversiones de la secuencia, claro que sí, PERO NO SU PARIDAD.
La inversión que era par sigue siendo par. Y la que era impar sigue siendo impar.

Conclusión: los movimientos permitidos en el "Jeu du Taquin" no alteran la paridad de la permutación del orden inicial de las 15 fichas.

Como la posición que debía alcanzarse para ganar los mil dólares es una permutación par y la posición de partida en que se vendía el juego es una permutación impar, el problema propuesto es imposible de resolver. Y la palabra tramposo está plenamente justificada, aunque en este caso haya que aplicársela a Sam Loyd, cuyos problemas ajedrecísticos contribuyeron a hacer de mí la persona que soy y no otra distinta.

¡Te pasaste de la raya, Sam, hiciste trampa! No mereces la bendición de Caissa, por mucho que llegases a ser el décimoquinto mejor tablero estadounidense de tu época.
Para los que no hacemos trampa ni al parchís, has dejado de ser un referente, Sam, que lo sepas.

Ah, por cierto, este asunto de la paridad... ¿sirve para algo serio, para algo que no sean las Torres de Hanoi o el Taquin?

La verdad es que sí.

Hay gente que se cree que está definiendo qué es un voltio al decir que es un amperio dividido por un ohmio. Igualito, igualito, hay quien se cree que está definiendo qué es un determinante de orden 2 al decir que es el producto del elemento 11 por el elemento 22 menos el producto del elemento 12 por el elemento 21.
Ambos cometen el mismo error: confunden "el concepto" con la operación que nos da el resultado numérico asociado al concepto.

Quien quiera definir correctamente qué es un voltio deberá decir que es la diferencia de potencial existente entre dos superficies equipotenciales de un campo eléctrico creado por una carga puntual cuando el desplazamiento entre las mismas de un culombio requiere un gasto energético de un julio.
Se puede dar una definición correcta basada en circuitos, claro que sí: la diferencia de potencial entre dos puntos de un circuito es un voltio cuando una corriente de un amperio circulando entre ellos disipa un julio por segundo.

¡¡Que no es lo mismo que la Ley de Ohm!!

Igualmente, quien quiera definir con el rigor que merecen los entes matemáticos qué es un determinante deberá decir - ejemplo de definición elegante donde los haya - lo que sigue:

Dada una matriz cuadrada A, llamaremos determinante de A a la suma algebraica de todos los productos que podamos formar tomando uno y solo un factor de cada fila y uno y solo un factor de cada columna, siendo cada producto positivo o negativo según sean respectivamente iguales o diferentes las paridades de las permutaciones de los subíndices primeros y segundos de los factores que lo forman.

Aplicando la definición al caso de orden 2, nos queda la fórmula:

En el primer producto, los primeros subíndices son 1 2 y los segundos son 1 2, la misma paridad, signo positivo.
En el segundo producto, los primeros subíndices son 1 2 y los segundos son 2 1, distinta paridad, signo negativo.

Exactamente igual se justifica la fórmula para orden 3:

Pero la fórmula NO ES la definición.
La operación que nos da el resultado NO ES el concepto.

En general y con la notación de Leibniz:

Vaya, qué cosas, el concepto de paridad sí que servía para algo más que para resolver puzzles, después de todo.



SOLUCIONES:

Solución del problema de ajedrez:
En la posición del diagrama, es más fácil ahogar al rey negro – lo que supone empatar la partida – que rematarlo. 1: Ab8 f2 (única) 2: Tc7 (bloqueando la acción del álfil para que el rey negro pueda moverse en lugar de quedar ahogado) Rh2 (única) 3: Th7++.
Ajedrecistas de alto nivel pueden quedarse un buen rato “empanados” delante de esta posición antes de que se les ocurra Ab8.

Solución del ejercicio:
Respecto al 1, están invertidos (por delante de él) el 4, el 5, el 2 y el 9. Ya van 4 inversiones. Respecto al 2, está invertido el 9. Ya van 5.
Total: 17. Impar.