Sam Loyd fue un ajedrecista, autor de rompecabezas, matemático recreativo y uno de los más grandes creadores de acertijos de Estados Unidos de América.
Comenzó a estudiar ingeniería civil hasta que abandonó sus estudios por volverse ajedrecista profesional. Llegó a ser el 15 mejor ajedrecista del mundo, siempre buscando jugadas complejas y bellas que asombraban al mundo.
Publicó diversos problemas de ajedrez, entre los cuales se encuentre el “Problema Excélsior” una verdadera obra de arte en el cual no importa que hagan las fichas negras, en a lo más 5 turnos su oponente habrá dado jaque mate. Una verdadera maravilla (vea Figura 1).
En 1878, Loyd propuso el popular rompecabezas denominado “juego del 15”, que en su momento creó gran conmoción y hasta nuestros días sigue generando mucho interés en nuestra sociedad.
Este rompecabezas consta de 15 fichas numeradas del 1 al 15 en orden ascendente que originalmente se encontraban dentro de una cajita de madera (véase Figura 2). Estas fichas únicamente son desplazables bajo movimientos laterales y verticales, uno a la vez y dependiendo que donde esté el espacio vacío (véase Figura 2). A estos desplazamientos les llamaremos movimientos válidos.
El objetivo del juego era lograr configuraciones de números en un orden preestablecido. Actualmente se puede encontrar este rompecabezas en muchas tiendas de juguetes con diferentes retos a conseguir en el rompecabezas, incluyendo uno llamado comúnmente el imposible.
Este inocente juego tiene un trasfondo matemático que Sam Loyd conocía muy bien y del cual se valió para retar a la sociedad de ese entonces, ofreciendo pagar mil dólares a quien lograra, mediante alguna secuencia de movimientos válidos, intercambiar el 14 y el 15 dejando a los demás números en su posición inicial (véase Figura 3). Esta posición es la que actualmente conocemos como el imposible.
Para entender porque esto no se puede lograr mediante movimientos válidos, llamaremos a las matemáticas, quienes nos mostrarán mediante operaciones muy básicas porque Sam Loyd nunca iba a tener que pagar esos mil dólares.
Decimos que una permutación de los números del 1 al n es una reordenación cualquiera a de la secuencia 1, 2, . . . , n. Por ejemplo, si tenemos los números 1, 2 y 3, estos números los podemos reordenar como 2, 1, 3 o 3, 2, 1. En total tenemos 6 formas de reordenar los números 1, 2 y 3. ¡Te invito a que intentes encontrar todas las posibles permutaciones!
Ahora, si al reordenar los números y con los números que ahora ocuparán la posición y , llamémosles y respectivamente y , entonces se dice que el par es una inversión, de lo contrario se dice que es una sucesión. Hagamos un ejemplo. Si tenemos lo números:
1,2,3,4 y los reordenamos como 2, 3, 1, 4.
¿El par es sucesión o inversión? Claramente es una inversión, pues 1<2 y en el reordenamiento ahora el 1 está en una posición mayor de la que se encuentra el 2. ¿El es sucesión o inversión? Nuevamente checamos las posiciones y nos damos cuenta que el 3 está primero que el 4, así que es una sucesión.
Si el número total de inversiones de una permutación es par, entonces se dice que la permutación es par; en caso contrario se dice que la permutación es impar. En el ejemplo del 1, 2, 3, 4 tenemos en total 2 inversiones, ¿las puedes localizar? Como hay un número par de inversiones, el ejemplo es una permutación par.
A cada posición del juego del 15 le podemos asociar una permutación de los números del 1 al 15, leyendo los números de izquierda a derecha y de arriba hacia abajo, sin tomar en cuenta la casilla vacía.
Por ejemplo, a la posición inicial del problema propuesto por Sam Loyd le corresponde la permutación 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. Esta permutación no tiene ninguna inversión, por lo tanto es una permutación par (porque el cero es un número par).
Y la permutación que había que obtener es 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, la cual solo tiene una sola inversión, que es (15, 14), por lo tanto es una permutación impar. ¿Se podrá llegar de una permutación par a una impar?
La clave está en los movimientos. Los movimientos horizontales no modifican en nada la permutación y tan sólo desplazan la casilla vacía dentro de la misma fila. En cambio si movemos un número hacia abajo el efecto sería que este número adelanta a los tres que le siguen, y además la casilla vacía pasará de una fila impar a una fila par, o viceversa.
Por ejemplo en la posición que se ilustra en la Figura 4 , si bajamos el 7 entonces éste adelanta al 11, al 6 y al 15. ¿Qué ocurre con la paridad de las permutaciones antes y después del movimiento? En primer lugar observemos que al bajar un número la única alteración del orden que se produce es la de ese número con los tres que le siguen.
Por lo tanto las únicas parejas que pueden cambiar su condición de inversión a sucesión, o viceversa, son (7,11), (7,6) y (7,15). De hecho, al bajar el 7 la inversión (7, 6) desaparece, pero en cambio aparecerán dos nuevas inversiones: (11, 7) y (15, 7).
Si el número a bajar está en inversión con (donde puede ser 1, 2 o 3) de los tres que le siguen (donde puede ser 1, 2 o 3), al efectuar el movimiento esas k inversiones desaparecerán, pero aparecerán nuevas. El cambio en el número total de inversiones será entonces , que siempre es impar.
Por lo tanto las permutaciones antes y después del movimiento serán de diferente paridad. De modo análogo, subir un número hace que este retroceda tres puestos y la permutación resultante tendrá paridad diferente a la de partida.
Ahora bien, si partimos de la posición inicial propuesta por Sam Loyd y llegamos a otra con la casilla vacía en la misma posición, el número de movimientos verticales realizados debe haber sido par (ya que la casilla vacía debe haber subido tantas veces como bajó). Por lo tanto la paridad de la permutación cambió un número par de veces, lo cual equivale a decir que quedó igual que al principio (o sea impar).
Esto demuestra que ni la permutación ordenada del 1 al 15, ni ninguna otra permutación par con la casilla vacía en la esquina inferior derecha puede ser obtenida a partir de la posición inicial de Sam Loyd.
Este es un bonito problema que ilustra que hacer matemáticas no es hacer operaciones extrañas y complejas. Basta hacer observaciones y proposiciones lógicas para llegar a resultados matemáticos.
MAT. GYIVAN ERICK LÓPEZ CAMPOS
UNIDAD ACADÉMICA DEL INSTITUTO DE MATEMÁTICAS
UNAM, CAMPUS JURIQUILLA
Referencias:
Nieto, J. H. (2005). Permutaciones y el Juego del 15. Boletín de la Asociación Matemática Venezolana, 259.
Hayes, R. (2001). The Sam Loyd 15-Puzzle. Trinity College Dublin, Department of Computer Science.
