Tercerca sesión (18 mar 2010)

Permutaciones y su "paridad"

• Una permutacion es un rearreglo de una lista de objetos, digamos los números 1, 2, ..., n. Por ejemplo: las permutaciones de 1, 2, 3 son: 123, 132, 213, 231, 312, 321.
• En general hay n!=1·2·3···n permutaciones de n objetos (1!=1, 2!=2, 3!=6, 4!=24, etc).
• Con cada permutacion se asocia una "paridad": par ó impar.
• Para calcular la paridad de una permutacion de n objetos se efectúan los siguientes pasos:
  • Se colocan una lista de los números del 1 al n en orden.
  • Debajo se coloca la permutación de estos números.
  • Se unen números iguales en ambas listas con curvas, de tal forma que (1) no se cruzan 3 (o mas) curvas en un punto, y (2) ninguna curva se cruze a si misma.
  • Se cuenta el número de intersecciones de las curvas. Si el número es par entonces se declara la permutacion "par" y si es impar entonces "impar".
  • Nota importante: hay muchas maneras de trazar las curvas que hemos descrito arriba; sin embargo, no importa cual haya sido ese trazo (siguiendo las 2 restricciones arriba), la paridad será la misma, o sea independiente de la manera de trazar las curvas.
  • Cuando se intercambian dos elementos en una permutación la paridad cambia.

• Es un reto popular que consiste de un cuadro de 4 x 4 en donde están ubicadas 15 fichas de 1 x 1 con los números del 1 al 15, dejando un cuadrito vacío. Cualquer ficha adyacente al cuadrito vacío la puedes mover al lugar vacío (dejando un lugar vacío donde estaba la ficha).
• El objetivo del juego es lograr diversos patrones de las fichas. Un tal reto es, empezando con las fichas en cierto patron, lograr intercambiar la posición de dos de las fichas (digamos 14 y 15), sin afectar la posición de las demas fichas. ¿Es posible cumplir tal reto?
• El reto es imposible de cumplir. Para ver esto matematicamente, se define un "invariante": una paridad asociado con cada patron de las fichas y que no cambia durante el juego. Luego checamos que el valor del invariante asociado con el patron inicial de las fichas es "par", y que se vuelve "impar" al intercambiar dos de las fichas, asi que la meta es inalcanzable.
• El invariante: es la suma de dos paridades, A y B (ver más abajo la definición de "suma de paridades").
  • La paridad A: se marca todos los 16 lugares de la tabla con los números 1 hasta 16 (digamos de la manera "estandar"). De este modo, cada patron de las fichas (incluyendo el vacio, que designamos como "ficha 16") define una permutacion de los numeros 1,2,3,...,16 . La paridad A entonces es la paridad de esta permutacion.
  • La paridad B: es la paridad de la ubicacion de la "ficha 16" (el lugar vacio): se marcan los lugares del tabla con "par" e "impar" de manera alternante (como blanco y negro en aljedrez) y la B es la paridad marcada en el cuadrado vacío.
  • Suma de paridades: par + par = par, par + impar = impar, impar + impar = impar.
• Luego se observa que al mover una ficha al lugar vacío, ambas paridades A y B cambian, así que su suma no cambia. Por otro lado, al intercambiar dos fichas (de 1 a 15), cambia solo la A, así que la suma A+B sí cambia.
• Este argumento no depende de que el cuadrado sea de 4 x 4. Podría ser cualquier forma (rectángulo u otro).