Invariantes

Un invariante es algo que ningún movimiento permitido altera. Desliza el rompecabezas, corta casillas del tablero o añade puentes a Königsberg, y la página mantendrá el invariante a la vista: la paridad del recuento de inversiones, negras contra blancas, las masas de tierra con un número impar de puentes. Cuando difiere entre el inicio y el objetivo, ninguna secuencia de movimientos llegará hasta allí.

Ejemplo resuelto — Invariantes

Inversiones	1
El invariante: inversiones mod 2	impar
Movimientos hasta resuelto	inalcanzable

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Invariantes

Un invariante es una cantidad que ningún movimiento permitido cambia. Si tiene un valor al principio y un valor distinto en el objetivo, el objetivo no se puede alcanzar, se intenten los movimientos que se intenten, y no hay que buscar nada para saberlo.

Qué significa cada símbolo

I: el invariante: aquí la paridad del recuento de inversiones, la diferencia entre casillas negras y blancas, o el número de masas de tierra con un número impar de puentes
d(v): el grado de una masa de tierra v: cuántos puentes terminan allí

De dónde viene la fórmula

Por qué un deslizamiento mantiene la paridad. Lee las ocho fichas fila por fila, ignorando el hueco. Un deslizamiento lateral no cambia ese orden de lectura en absoluto. Un deslizamiento vertical mueve una ficha tres posiciones a lo largo del mismo, pasando por las dos fichas entre su antigua casilla y la nueva. Cada uno de esos dos pares gana o pierde una inversión, por lo que el recuento cambia en −2, 0 o +2, nunca en un número impar. Resuelto tiene 0, por lo que una posición con un recuento impar no se puede alcanzar. Que toda posición con un recuento par se pueda alcanzar es la mitad más difícil: para el juego del 8 la búsqueda de la página lo muestra directamente.
Por qué un dominó mantiene la diferencia. En un tablero de ajedrez los vecinos de toda casilla son del otro color, por lo que un dominó, que cubre dos casillas vecinas, cubre una negra y una blanca. Poner dominós, por lo tanto, nunca cambia las negras menos las blancas entre las casillas descubiertas. Un cubrimiento terminado no deja nada descubierto, una diferencia de 0, por lo que necesita una diferencia de 0 al principio: tantas casillas de un color como del otro.
Por qué como máximo dos masas de tierra impares. Sigue el recorrido. Cada vez que pasa por una masa de tierra llega por un puente y se va por otro, de forma que los puentes en una masa de tierra se usan en pares, salvo en el inicio, donde uno se usa saliendo, y en el final, donde uno se usa llegando. Si el recorrido acaba donde empezó, toda masa de tierra tiene un número par de puentes; en caso contrario, exactamente el inicio y el final tienen un número impar. Lo recíproco también se cumple cuando los puentes conectan todo, y la página encuentra el recorrido construyéndolo en bucles y empalmándolos.

La mitad de las posiciones de un rompecabezas deslizante de 3 × 3 son inalcanzables, y puedes saber de qué mitad se trata sin tener que buscar 🖖

Pulsa 7 y 8 intercambiados e intenta resolverlo. Cuenta los pares de fichas que están en orden incorrecto, leyendo fila por fila: aquí uno, 8 antes que 7. Un deslizamiento lateral deja ese recuento igual, y un deslizamiento vertical hace pasar una ficha por delante de otras dos, cambiándolo en 0 o en 2. Por tanto, el recuento se mantiene impar para siempre, y la posición resuelta tiene 0. La página también ha explorado cada posición desde la resuelta: 181.440 de las 362.880 disposiciones son alcanzables, exactamente las que tienen un recuento par, y las dos más lejanas necesitan 31 movimientos. El juego del 15 arrasó en Estados Unidos en 1880, y en la década de 1890 Sam Loyd ofreció 1.000 $ por deshacer un intercambio de 14 y 15, un premio que nadie pudo ganar jamás.

Corta dos esquinas opuestas de un tablero de ajedrez y no sobrevivirá ningún cubrimiento con dominós 🖖

Pulsa Esquinas opuestas. El tablero completo se puede cubrir con 32 dominós de 12.988.816 maneras. Corta dos esquinas opuestas y no se podrá cubrir en absoluto: ambas esquinas son del mismo color, por lo que quedan 30 casillas de un color frente a 32 del otro, y cada dominó cubre una de cada. En su lugar, corta las dos esquinas de los extremos de un borde, una de cada color, y habrá 2.436.304 cubrimientos. Luego pulsa Esquina bloqueada: 30 y 30, un equilibrio perfecto, y aun así ninguno, porque la casilla de la esquina no tiene ningún vecino restante. El recuento de colores puede demostrar que un tablero es imposible; nunca puede demostrar que sea posible.

El recorrido de Königsberg fracasa por un recuento que puedes hacer mentalmente 🖖

Pulsa Königsberg. La isla tiene 5 puentes y cada una de las otras tres masas de tierra tiene 3. Un recorrido que cruce cada puente una vez llega a cada masa de tierra por la que pasa y sale de ella, usando sus puentes en pares; solo pueden sobrar donde el recorrido empieza y donde termina. Así que, como máximo, dos masas de tierra pueden tener un número impar, y aquí lo tienen las cuatro. Euler zanjó la cuestión en un artículo escrito en 1735. Añade un puente entre las dos orillas con el + al lado de B–C: quedan dos masas de tierra impares, y la página encuentra el recorrido, de A a D. Los cuatro recuentos siempre suman el doble del número de puentes, y por eso los impares siempre vienen en pares.

Problema resuelto al detalle

¿Podría alguien ganar los 1.000 $ de Sam Loyd? 4 pasos
En el tablero de 4 × 4, intercambia solo 14 y 15 y deja el hueco en su esquina. Sam Loyd ofreció 1.000 $ a cualquiera que pudiera deslizarlo hasta resolverlo. ¿Se podía hacer?

Abre este problema en la herramienta
1. En el tablero de 3 × 3 de esta página, el invariante era la paridad del recuento de inversiones:
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. En un tablero de cuatro casillas de ancho, un deslizamiento vertical hace pasar una ficha por delante de otras tres, por lo que el recuento cambia en un número impar, y el hueco cambia de fila:
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Todo deslizamiento invierte ambas paridades o ninguna, por lo que su suma, tomada mod 2, nunca cambia:
  
  $I + row of the blank (mod 2) never changes$
4. Compara las dos posiciones, con el hueco en la fila 4 en ambas:
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Respuesta

Nadie podía ganarlo: el intercambio se encuentra en el lado equivocado del invariante. Exactamente la mitad de las disposiciones de 16!, 10.461.394.944.000, se pueden alcanzar desde la resuelta. Pulsa 7 y 8 intercambiados para ver la versión de 3 × 3 de la misma trampa.

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

Ruta de aprendizaje

Métodos de demostración

Referencias (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.