Matemática e teoria

Por que nem todo jogo do 15 tem solução — a regra de paridade

Metade de todas as disposições do jogo do 15 não tem solução. Sam Loyd ofereceu 1000 dólares em 1880 pela impossível. Veja a matemática: paridade de permutação, contagem de inversões e por que a linha do espaço vazio importa.

Em 1880, o criador de quebra-cabeças norte-americano Sam Loyd anunciou um prêmio de 1000 dólares para quem resolvesse um jogo do 15 específico: a disposição padrão de 1 a 15 com o 14 e o 15 trocados. A febre dos quebra-cabeças já tomava conta dos Estados Unidos e da Europa, e a jogada publicitária de Loyd jogou lenha na fogueira. Milhares tentaram. Ninguém ganhou.

Havia um motivo para ninguém ganhar. O tabuleiro de Loyd era comprovadamente insolúvel, e a demonstração é elementar o bastante para caber numa página. Este artigo é essa página.

A afirmação

Exatamente metade das 16! ≈ 20.922.789.888.000 maneiras de dispor quinze peças e um espaço vazio num tabuleiro 4×4 pode ser levada até o objetivo padrão. A outra metade não pode. O "14 e 15 trocados" de Loyd está na metade insolúvel.

Isso vale de forma geral. Em todo quebra-cabeça deslizante N×N, metade das disposições é insolúvel. O jogo do 8 3×3 tem 9!/2 = 181.440 tabuleiros solúveis num total de 362.880; o jogo do 24, o jogo do 35 e assim por diante seguem a mesma regra.

Inversões

A demonstração precisa de uma definição. Leia as peças em ordem de leitura (da esquerda para a direita na linha 1, depois a linha 2, depois a 3, depois a 4) e ignore o espaço vazio. Você obtém uma sequência de quinze números.

Uma inversão é um par (a, b) em que a aparece antes de b na sequência, mas a > b. Conte todos esses pares na sequência inteira. Esse total é o número de inversões do tabuleiro.

Exemplo: o estado-objetivo 1, 2, 3, …, 15 tem zero inversões. O "14 e 15 trocados" de Loyd tem a sequência 1, 2, 3, …, 13, 15, 14, com exatamente uma inversão (o par 15, 14).

O lema-chave: um deslize altera a paridade de forma controlada

O que acontece com a contagem de inversões quando você faz um movimento legal?

Resumindo: um deslize horizontal preserva a paridade da contagem de inversões (par ou ímpar). Um deslize vertical inverte essa paridade.

A linha do espaço vazio também muda nos deslizes verticais

Acompanhe a linha do espaço vazio, contando as linhas a partir do topo. Um deslize horizontal mantém o vazio na mesma linha. Um deslize vertical leva o vazio uma linha para cima ou para baixo, então a paridade da linha do vazio muda (linha par ↔ linha ímpar).

Agora temos duas coisas que mudam juntas:

A soma das duas é, portanto, invariante em qualquer deslize legal. Encontramos uma grandeza conservada.

O teorema da paridade

Defina o invariante:

P = (contagem de inversões) + (número da linha do vazio, contado a partir de baixo, começando em 1)

Esta é a grandeza conservada. Em cada deslize legal, P muda por um número par, então sua paridade (par ou ímpar) nunca muda.

O estado-objetivo tem zero inversões e o vazio na linha 1 contando de baixo, portanto P = 1 (ímpar). Qualquer tabuleiro com P par é inalcançável a partir do objetivo e, da mesma forma, o objetivo é inalcançável a partir desse tabuleiro.

Isso dá um teste de solubilidade claro para o jogo do 15:

  1. Leia as peças em ordem de linhas, ignorando o vazio.
  2. Conte as inversões.
  3. Conte a linha do vazio a partir de baixo (1, 2, 3 ou 4).
  4. Some. Se a soma for ímpar, o tabuleiro é solúvel. Se for par, não é.

O "14 e 15 trocados" de Loyd tem 1 inversão e o vazio na linha 1 contando de baixo: soma 2, par, insolúvel.

Como isso funciona em outros tamanhos

A regra de paridade N×N depende de N ser par ou ímpar. O enunciado geral:

Num 3×3, o teste se resume a "há um número par de inversões?". É mais simples do que a versão 4×4, e você decora em um minuto.

Uma consequência interessante

Como exatamente metade das disposições é solúvel, uma mistura aleatória seguida do teste de paridade é mais rápida do que uma mistura aleatória seguida de tentar resolver. Os aplicativos que precisam garantir posições iniciais solúveis fazem uma de duas coisas:

Se algum dia você jogar um quebra-cabeça deslizante e achar que é impossível, seja lá o que você fizer, foi o aplicativo que gerou errado. A culpa não é sua, e não é nenhum mistério do universo.

A nota de rodapé sobre Sam Loyd

O prêmio de 1000 dólares de Loyd é uma das pegadinhas mais bem documentadas da história dos quebra-cabeças. O matemático que provou a insolubilidade, de forma independente, foi William Johnson e William Story (1879, American Journal of Mathematics) ou o próprio Loyd, dependendo da versão em que você acredita. Loyd era famoso pela autopromoção e reivindicou várias invenções que não eram dele; o próprio jogo do 15 foi inventado por Noyes Chapman em 1874, seis anos antes da jogada publicitária de Loyd.

O que Loyd de fato contribuiu foi o prêmio, a publicidade e a variante insolúvel. Uma contribuição útil, ainda que não fosse a que ele anunciava.

Por · Atualizado