Para comprender lo que ocurre, recordemos que una permutación de los números del 1 al n es una reordenación cualquiera a1, a2,...,an de la secuencia 1,2,...,n. Si i < j y ai > aj se dice que el par (ai,aj) es una inversión de la permutación a1, a2,...,an. Una permutación es par si el número total de sus inversiones lo es; en caso contrario se dice que la permutación es impar. Es claro que 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 en la caja de izquierda a derecha y de arriba hacia abajo, sin tomar en cuenta al espacio vacío. 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, 15, 14. Esta permutación tiene una sola inversión, a saber el par (15, 14), por lo tanto es impar. La permutación que había que obtener para ganar el premio es sencillamente 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, la cual no tiene inversiones y por lo tanto es par (ya que 0 es un número par).
Ahora veamos qué ocurre cuando hacemos un movimiento en el juego del 15. Es claro que 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á que este número adelanta a los tres que le siguen, y además el espacio vacío pasará de una fila impar a una par, o viceversa. Por ejemplo en la posición
|
5 |
3 |
1 |
4 |
|
10 |
8 |
7 |
11 |
|
6 |
15 |
2 | |
|
9 |
13 |
14 |
12 |
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 inversiones que pueden cambiar son las que relacionen al número movido con los otros tres. Así al bajar el 7 la inversión (7, 6) desaparecerá; pero en cambio aparecerán dos nuevas: la (11, 7) y la (15, 7). En general si el número a bajar está en inversión con k de los tres que le siguen (donde k puede ser 0, 1, 2 o 3), al efectuar el movimiento esas k inversiones desaparecerán, pero aparecerán 3 - k nuevas. El cambio en el número total de inversiones será (3 - k) - k = 3 - 2k, 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 éste 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 el espacio vacío en la misma posición, el número de movimientos verticales realizados debe haber sido par (ya que el espacio vacío 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 el espacio vacío en la esquina inferior derecha puede ser obtenida a partir de la posición inicial, y Sam Loyd en ningún momento corrió el riesgo de tener que pagar mil dólares.
Como se sabe hay 15! = 1307674368000 permutaciones de los números del 1 al 15, y exactamente la mitad son pares (la otra mitad impares). Puede probarse que a partir de la posición inicial de Sam Loyd puede obtenerse cualquier permutación impar con el hueco en la cuarta o en la segunda fila, y cualquier permutación par con el hueco en la primera o tercera filas. Por ejemplo, puede obtenerse la posición
|
1 |
2 |
3 | |
|
4 |
5 |
6 |
7 |
|
8 |
9 |
10 |
11 |
|
12 |
13 |
14 |
15 |
En cambio no se pueden obtener permutaciones impares con el hueco en la primera o tercera filas, ni permutaciones pares con el hueco en la segunda o en la cuarta filas. En resumen, el conjunto de todas las posiciones del juego del quince se puede dividir en dos clases, tales que de una posición se puede pasar mediante movimientos válidos a cualquier otra de la misma clase, pero a ninguna de la otra clase.
Para finalizar, un ejercicio interesante para mentes inquietas: analizar la generalización de este juego con los números desde 1 hasta n2 - 1 colocados en un cuadrado de nxn.
Volver a la página inicial del Juego del 15
Volver a la página principal