Invariantes

Um invariante é algo que nenhum movimento permitido altera. Deslize as peças, recorte quadrados do tabuleiro ou adicione pontes em Königsberg, e a página manterá o invariante à vista: a paridade do número de inversões, as casas pretas contra as brancas, as porções de terra com um número ímpar de pontes. Quando este valor difere entre o início e o objetivo, não existe sequência de movimentos que lá chegue.

Exemplo resolvido — Invariantes

Inversões	1
O invariante: inversões mod 2	ímpar
Movimentos até resolver	inatingível

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Invariantes

Um invariante é uma grandeza que nenhum movimento permitido altera. Se apresentar um valor no início e um valor diferente no objetivo, esse objetivo será inatingível, independentemente dos movimentos tentados. Não é preciso fazer nenhuma busca para o saber.

O que significa cada símbolo

I: o invariante: aqui, a paridade do número de inversões, a diferença entre os quadrados pretos e brancos, ou o número de porções de terra com um número ímpar de pontes
d(v): o grau de uma porção de terra v: quantas pontes terminam lá

De onde vem a fórmula

Por que um deslizamento mantém a paridade. Leia as oito peças linha a linha, ignorando o espaço vazio. Um deslizamento lateral não altera essa ordem de leitura. Um deslizamento vertical move uma peça três posições ao longo da mesma, passando por duas peças que se encontram entre o seu quadrado antigo e o novo. Cada um desses dois pares ganha ou perde uma inversão. A contagem altera-se em −2, 0 ou +2, mas nunca num valor ímpar. A solução tem 0, por isso, uma posição com uma contagem ímpar não pode ser alcançada. Provar que todas as posições com uma contagem par são alcançáveis é a parte mais difícil. No caso do jogo do 8, a busca desta página demonstra-o de forma direta.
Por que um dominó mantém a diferença. Num tabuleiro de xadrez, os vizinhos de cada quadrado são da cor oposta. Um dominó, ao cobrir dois quadrados vizinhos, cobre um preto e um branco. Colocar dominós nunca altera a diferença entre pretos e brancos nos quadrados ainda descobertos. Uma cobertura completa não deixa nada a descoberto, o que representa uma diferença de 0. Para isso, precisa de ter uma diferença de 0 no início: tantos quadrados de uma cor como da outra.
Por que há no máximo duas porções de terra ímpares. Siga o passeio. Sempre que passa por uma porção de terra, chega por uma ponte e parte por outra. As pontes de uma porção de terra são assim usadas aos pares. As exceções são o início, onde uma é usada para partir, e o fim, onde uma é usada para chegar. Se o passeio terminar onde começou, todas as porções de terra terão um número par de pontes. Caso contrário, exatamente o início e o fim terão um número ímpar. O inverso também é válido quando as pontes unem tudo. A página encontra o passeio construindo-o em ciclos e juntando-os.

Metade das posições de um quebra-cabeça deslizante 3 × 3 nunca pode ser alcançada, e é possível saber qual metade sem procurar 🖖

Pressione 7 e 8 trocados e tente resolvê-lo. Conte os pares de peças que se encontram na ordem errada, lendo linha a linha: aqui há um, o 8 antes do 7. Um deslizamento lateral mantém essa contagem inalterada. Um deslizamento vertical faz uma peça passar por duas outras, alterando o valor em 0 ou 2. Portanto, a contagem permanece ímpar para sempre, e a solução tem 0. A página também analisou todas as posições a partir da solução: 181.440 das 362.880 configurações são alcançáveis. São precisamente aquelas com uma contagem par, e as duas mais distantes exigem 31 movimentos. O jogo dos 15 invadiu a América em 1880 e, na década de 1890, Sam Loyd ofereceu $1.000 a quem conseguisse desfazer uma troca entre o 14 e o 15. Um prémio que ninguém jamais poderia vencer.

Recorte dois cantos opostos de um tabuleiro de xadrez e nenhuma cobertura com dominós sobrevive 🖖

Pressione Cantos opostos. O tabuleiro completo pode ser coberto por 32 dominós de 12.988.816 formas. Recorte dois cantos opostos e será impossível cobri-lo: ambos têm a mesma cor, logo, restam 30 quadrados de uma cor contra 32 da outra. Como cada dominó cobre um de cada cor, a tarefa torna-se impossível. Se, em vez disso, recortar os dois cantos nas extremidades do mesmo lado, um de cada cor, existirão 2.436.304 coberturas. A seguir, pressione Canto isolado: 30 e 30, perfeitamente equilibrado, mas continua sem solução, porque o quadrado do canto ficou sem nenhum vizinho. A contagem de cores consegue provar que um tabuleiro é impossível. Nunca consegue provar que é possível.

O passeio de Königsberg falha por uma contagem que se faz de cabeça 🖖

Pressione Königsberg. A ilha tem 5 pontes e cada uma das outras três porções de terra tem 3. Um passeio que atravesse cada ponte uma única vez chega e parte de cada porção de terra por onde passa. As pontes são usadas aos pares, e apenas no início e no fim do trajeto pode sobrar uma. Logo, no máximo duas porções de terra podem ter um número ímpar, e aqui as quatro têm. Euler resolveu o problema num artigo escrito em 1735. Adicione uma ponte entre as duas margens no + junto a B–C: restam duas porções de terra ímpares e a página encontra o passeio, de A a D. As quatro contagens somam sempre o dobro do número de pontes. É por isso que os ímpares surgem sempre aos pares.

Problema resolvido na íntegra

Alguém conseguiria ganhar os $1.000 de Sam Loyd? 4 passos
No tabuleiro de 4 × 4, troque apenas o 14 e o 15 e deixe o espaço vazio no seu canto. Sam Loyd ofereceu $1.000 a quem conseguisse deslizar as peças de volta à solução. Seria isso possível?

Abrir este problema na ferramenta
1. No tabuleiro de 3 × 3 desta página, o invariante era a paridade do número de inversões:
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. Num tabuleiro com quatro de largura, um deslizamento vertical faz uma peça passar por três outras. A contagem sofre uma alteração por um valor ímpar e o espaço vazio muda de linha:
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Cada deslizamento inverte ambas as paridades ou nenhuma, logo a sua soma, calculada em mod 2, nunca se altera:
  
  $I + row of the blank (mod 2) never changes$
4. Compare as duas posições, tendo ambas o espaço vazio na linha 4:
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Resposta

Ninguém poderia ganhar: a troca encontra-se do lado errado do invariante. Exatamente metade das 16! configurações, 10.461.394.944.000, podem ser alcançadas a partir da solução. Pressione 7 e 8 trocados para a versão de 3 × 3 da mesma armadilha.

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

Percurso de aprendizagem

Métodos de demonstração

Referências (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.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.