Juegos Matematicos
Páginas: 9 (2206 palabras)
Publicado: 14 de octubre de 2012
julio
Parte I: Juegos Matemáticos:
Juego del 15:
En 1878 Sam Loyd (1841–1911), uno de los más grandes creadores de acertijos que han existido, propuso un rompecabezas que causó verdadero furor en su época y ha mantenido su popularidad hasta nuestros días. La versión original consistía en una caja cuadrada que contenía quince piezas cuadradas, numeradas del 1 al 15, dispuestas como seve en el siguiente diagrama:
|1 |2 |3 |4 |
|5 |6 |7 |8 |
|9 |10 |11 |12 |
|13 |15 |14 | |
Observe que la casilla inferior derecha está vacía, y si los números se leen de izquierda a derecha y de arriba hacia abajo entonces están ordenados en forma creciente, excepto por el 15 y el 14 que aparecen transpuestos.Un movimiento válido consiste en deslizar uno de los números horizontal o verticalmente adyacentes a la casilla vacía hasta ocuparla, dejando vacante la casilla ocupada originalmente por la pieza movida. En la posición inicial hay solo dos movimientos válidos, que consisten en mover el 12 o el 14 hasta ocupar la casilla inferior derecha. Pues bien, Sam Loyd ofreció pagar mil dólares a quienlograra, 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. En otras palabras, si llamamos posición normal a la que tiene los quince números ordenados en forma creciente y con la casilla inferior derecha vacía, la propuesta de Sam Loyd fue hallar una secuencia de movimientos válidos que transforme la posición de la Figura 1en la posición normal.
El premio ofrecido desató un verdadero frenesí por hallar la solución. En su obra póstuma [2, p. 235] el propio Sam Loyd narra, de manera humorística, cómo volvió “loco al mundo entero con una pequeña caja con piezas movibles”.
Una persona común y corriente se pondría a mover números de casillas como estime conveniente, teniendo como consecuencia nunca llegar al éxito:en realidad no existe, y nadie pudo cobrar el premio ofrecido por Sam Loyd!
Los matemáticos no tardaron mucho en darse cuenta de esto, como lo prueban dos artículos [3, 5] aparecidos en 1879 en el “American Journal of Mathematics.”
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 entonces se dice que el par (ai, aj ) es una inversión, de lo contrario se dice 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. El número total de permutaciones de los números del 1 al n es n! = 1 · 2 · 3 · · · n. Si n > 1 es fácil verque la mitad de las permutaciones son pares y la otra mitad son impares (en efecto, la transposición de los dos primeros elementos de una permutación establece una bisección entre las permutaciones pares y las impares). 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 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, 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 era simplemente la sucesión ordenada de los 15 primeros númerosnaturales, la cual no tiene inversiones y por lo tanto es par. Ahora veamos qué ocurre cuando hacemos un movimiento válido. Es claro que los movimientos horizontales no modifican en nada la permutación y tan solo desplazan la casilla vacía dentro de la misma fila.
|5 |3 |1 |4 |
|10 |8 |7 |11 |
|6 |15 | |2 |
|9...
Parte I: Juegos Matemáticos:
Juego del 15:
En 1878 Sam Loyd (1841–1911), uno de los más grandes creadores de acertijos que han existido, propuso un rompecabezas que causó verdadero furor en su época y ha mantenido su popularidad hasta nuestros días. La versión original consistía en una caja cuadrada que contenía quince piezas cuadradas, numeradas del 1 al 15, dispuestas como seve en el siguiente diagrama:
|1 |2 |3 |4 |
|5 |6 |7 |8 |
|9 |10 |11 |12 |
|13 |15 |14 | |
Observe que la casilla inferior derecha está vacía, y si los números se leen de izquierda a derecha y de arriba hacia abajo entonces están ordenados en forma creciente, excepto por el 15 y el 14 que aparecen transpuestos.Un movimiento válido consiste en deslizar uno de los números horizontal o verticalmente adyacentes a la casilla vacía hasta ocuparla, dejando vacante la casilla ocupada originalmente por la pieza movida. En la posición inicial hay solo dos movimientos válidos, que consisten en mover el 12 o el 14 hasta ocupar la casilla inferior derecha. Pues bien, Sam Loyd ofreció pagar mil dólares a quienlograra, 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. En otras palabras, si llamamos posición normal a la que tiene los quince números ordenados en forma creciente y con la casilla inferior derecha vacía, la propuesta de Sam Loyd fue hallar una secuencia de movimientos válidos que transforme la posición de la Figura 1en la posición normal.
El premio ofrecido desató un verdadero frenesí por hallar la solución. En su obra póstuma [2, p. 235] el propio Sam Loyd narra, de manera humorística, cómo volvió “loco al mundo entero con una pequeña caja con piezas movibles”.
Una persona común y corriente se pondría a mover números de casillas como estime conveniente, teniendo como consecuencia nunca llegar al éxito:en realidad no existe, y nadie pudo cobrar el premio ofrecido por Sam Loyd!
Los matemáticos no tardaron mucho en darse cuenta de esto, como lo prueban dos artículos [3, 5] aparecidos en 1879 en el “American Journal of Mathematics.”
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 entonces se dice que el par (ai, aj ) es una inversión, de lo contrario se dice 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. El número total de permutaciones de los números del 1 al n es n! = 1 · 2 · 3 · · · n. Si n > 1 es fácil verque la mitad de las permutaciones son pares y la otra mitad son impares (en efecto, la transposición de los dos primeros elementos de una permutación establece una bisección entre las permutaciones pares y las impares). 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 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, 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 era simplemente la sucesión ordenada de los 15 primeros númerosnaturales, la cual no tiene inversiones y por lo tanto es par. Ahora veamos qué ocurre cuando hacemos un movimiento válido. Es claro que los movimientos horizontales no modifican en nada la permutación y tan solo desplazan la casilla vacía dentro de la misma fila.
|5 |3 |1 |4 |
|10 |8 |7 |11 |
|6 |15 | |2 |
|9...
Leer documento completo
Regístrate para leer el documento completo.