In partnership with

ED 029

Mil dólares pelo catorze e o quinze

Sam Loyd ofereceu mil dólares a quem trocasse duas peças de lugar deslizando, e a caixinha guardava uma trava que ninguém enxergava.

Uma caixa de madeira com quinze peças numeradas embaralhadas e um espaço vazio no canto.

As quinze peças e o espaço vazio

▼

Por que o catorze e o quinze não trocam de lugar na caixinha, se qualquer outra peça vai parar onde você quiser? Porque a troca inverte uma paridade do tabuleiro, e nenhum deslize de peça inverte paridade de volta.

Em 1880 essa impossibilidade valia mil dólares. Sam Loyd, o criador de passatempos mais conhecido dos Estados Unidos na época, anunciou o prêmio para quem apresentasse a sequência de deslizes capaz de colocar as quinze peças em ordem crescente partindo de um tabuleiro em que só o catorze e o quinze aparecem invertidos. Mil dólares comprava uma casa modesta naquele ano. A oferta ficou de pé por muito tempo e o dinheiro nunca saiu do bolso dele.

A caçada ao prêmio foi coletiva e barulhenta. Lojistas contavam que fregueses passavam a tarde empurrando peças no balcão, patrões reclamavam de escritórios parados, e cartas com sequências supostamente vencedoras chegavam às redações de jornal. Nenhuma dessas cartas sobrevivia à conferência. Todas escorregavam no mesmo ponto: descreviam um movimento que a caixa física não permite, como levantar uma peça e recolocá-la noutro buraco.

O detalhe cruel do anúncio é que a resposta já circulava impressa antes dele. Em 1879, William Woolsey Johnson e William Story publicaram no American Journal of Mathematics uma nota curta sobre o brinquedo, demonstrando que as configurações do tabuleiro se dividem em duas metades e que nenhuma sequência de deslizes leva de uma metade à outra. Loyd ofereceu dinheiro por um trajeto que a matemática já tinha declarado inexistente um ano antes.

Quem gastou tardes na caixa não tinha como saber. E o dinheiro só ficava seguro por causa de uma propriedade que sobrevive a qualquer deslize: uma quantidade que o tabuleiro carrega o tempo inteiro e que nenhum movimento legal consegue mudar. Encontrar essa quantidade, e provar que ela trava o prêmio, é o trabalho de hoje.

Antes das peças de madeira, fica de pé o mapa das quatro margens de Königsberg, as sete pontes sobre o Pregel e o passeio que os moradores tentaram fechar durante décadas.

Continue lendo ↓

I A resposta de ontem

Quatro margens ímpares e o passeio que não existe

Nenhum passeio cruza as sete pontes uma vez cada. A prova sai de quatro números escritos numa folha, e nenhuma tentativa de rota participa dela.

Conte as pontes que chegam a cada pedaço de terra. A ilha de Kneiphof recebe cinco. A margem norte recebe três. A margem sul recebe três. A língua de terra a leste recebe três. Some: cinco mais três mais três mais três dá catorze, o dobro de sete, porque cada ponte é contada nas duas pontas. A soma bate, então o desenho está certo.

Os quatro números são ímpares. Um passeio tem um começo e um fim, e só esses dois lugares aceitam número ímpar de pontes. Quatro candidatos disputando duas vagas: o passeio não existe, e o assunto fecha aqui.

O argumento por trás dessa contagem cabe numa frase. Qualquer pedaço de terra que você atravesse no meio do caminho consome duas pontes por visita, uma para entrar e outra para sair. Visitas gastam pontes aos pares. Um total ímpar sempre deixa uma ponte solta, e a única maneira de acomodar essa sobra é começar ou terminar o passeio ali.

Onde a solução realmente escapa

Quem rabisca rotas fica preso numa armadilha silenciosa. Cada tentativa que falha parece azar da vez, e a folha vai enchendo de riscos sem que a conclusão apareça. Mais de cinco mil sequências cabem no problema, e percorrer todas ainda deixaria a dúvida de ter esquecido alguma.

O segundo tropeço é achar que a resposta precisa ser um caminho. Provar que caminho nenhum existe também responde, e responde com mais força: elimina de uma vez as cinco mil tentativas e todas as que alguém inventasse depois.

O terceiro tropeço é desenhar a cidade em vez do esqueleto. Ruas, catedral, castelo e a curva do rio ocupam a folha e escondem o único dado que decide, o número de traços que sai de cada ponto.

Guarde o formato da solução, porque ele reaparece agora com outra roupa. O trabalho foi achar uma quantidade que o problema carrega de graça, ver que ela não muda com nenhum movimento permitido, e comparar o começo com o alvo. Nas pontes, a quantidade era a paridade do número de pontes por margem.

O enigma de agora usa a mesma chave numa caixa de madeira com quinze peças numeradas. Existe uma quantidade escondida ali, e ela custou mil dólares a quem apostou contra.

II O Enigma do dia

Catorze e quinze, mil dólares pela troca

Uma caixa quadrada guarda quinze peças numeradas de 1 a 15 e um espaço vazio. As peças estão em ordem crescente, lendo da esquerda para a direita e de cima para baixo, com uma exceção: o 14 ocupa o lugar do 15 e o 15 ocupa o lugar do 14. O vazio está no canto inferior direito. Deslizando peças para o vazio, uma por vez, existe alguma sequência que deixe as quinze em ordem crescente com o vazio de volta no canto? Se existe, qual? Se não existe, por quê?

As regras da caixa são estritas e vale reler antes de continuar. Um movimento consiste em empurrar para o espaço vazio uma peça vizinha por lado, nunca na diagonal. A peça e o vazio trocam de posição. Você pode fazer quantos movimentos quiser, na ordem que quiser, e pode passar pela mesma configuração várias vezes. O que a caixa proíbe é tirar peça do tabuleiro, girar a caixa e encaixar peça em posição não vizinha.

Onde quase todo mundo trava

O primeiro erro é confiar no cansaço como prova. Depois de uma hora empurrando peças, a sensação de impossível chega, mas sensação não decide nada. Aritmética decide.

O segundo erro é procurar uma sequência mais longa. A intuição sugere que o caminho existe e está escondido atrás de muitos movimentos, então quem tenta aumenta o número de deslizes achando que a solução aparece pelo volume. O número de configurações alcançáveis passa de dez trilhões, e nenhuma força bruta humana varre essa quantidade.

O terceiro erro é o mais caro, e é ele que mantinha o prêmio de Loyd intacto. É procurar a resposta na trajetória quando ela mora numa quantidade fixa. Enquanto você olha para os movimentos, a trava fica invisível; quando você olha para o que os movimentos preservam, a trava aparece em dois minutos.

Toda vez que uma peça desliza, ela troca de posição com o vazio, e uma troca de duas coisas inverte a paridade da permutação. O vazio também anda uma casa, e a paridade da distância dele ao canto se inverte junto. As duas inversões acontecem sempre no mesmo movimento, então a soma delas nunca muda.

Pense no que essa quantidade impõe. No tabuleiro de partida, o 14 e o 15 estão trocados, ou seja, uma troca separa a posição inicial da posição alvo. O vazio, por sua vez, começa no canto e precisa terminar no canto, então ele anda um número par de casas. Agora junte as duas contas e veja se o alvo cabe na mesma metade.

A pergunta pede as duas partes. Diga quantas trocas de pares separam a posição inicial do arranjo final e se esse número é par ou ímpar. Depois responda se a sequência premiada existe, e sustente a resposta com a quantidade preservada, não com a quantidade de tentativas que falharam na sua mesa.

Quem banca a edição de hoje

Talk to your AI tools the way you'd talk to a colleague.

You don't send a colleague a three-word brief. You explain the context, the constraints, what you've already tried. But typing all that into ChatGPT takes forever — so you don't.

Wispr Flow lets you speak your prompts instead. Talk through your thinking naturally and get clean, paste-ready text. No filler words. No cleanup. Just detailed prompts that actually get you useful answers on the first try.

Millions of users worldwide. Works system-wide on Mac, Windows, and iPhone.

Try Wispr Flow free

Patrocinadores mantêm a edição gratuita

III Sequência

Contar as trocas antes de deslizar

O material é uma folha, uma caneta e cinco minutos, e o exercício funciona com qualquer quebra-cabeça de peças deslizantes que você tenha em casa ou no celular. Escreva numa linha só a ordem em que as peças aparecem no tabuleiro, lendo da esquerda para a direita e de cima para baixo, e ignore o espaço vazio nessa linha.

A linha faz metade do serviço porque transforma um objeto de madeira numa sequência de números, e sequência de números aceita contagem. É a mesma manobra do passeio pelas pontes: jogar fora a forma física e ficar com a estrutura.

1. Conte quantas trocas de duas peças bastam para levar a sua linha até a ordem crescente. Escolha o menor número que você conseguir, e não se preocupe se um amigo achou um caminho diferente: a quantidade pode variar, a paridade dela nunca varia.

2. Conte quantas casas o vazio precisa andar para chegar ao canto inferior direito, contando na horizontal e na vertical, sem diagonal. Some as duas contas do passo 1 e do passo 2 e olhe só para o resultado ser par ou ímpar.

3. Compare com zero. Soma par: a posição é alcançável, e existe sequência de deslizes que resolve o tabuleiro. Soma ímpar: a posição é inalcançável, nenhuma sequência resolve, e o assunto está encerrado sem empurrar peça nenhuma.

"Os habitantes mais antigos da Terra dos Quebra-Cabeças hão de lembrar como, no começo dos anos setenta, deixei o mundo inteiro louco por causa de uma caixinha de peças móveis que ficou conhecida como o Quebra-Cabeça do 14-15."

Sam Loyd, Cyclopedia of 5000 Puzzles, Tricks and Conundrums, 1914.

Repare no que a frase de Loyd faz. Ela conta a febre, não conta a nota de Johnson e Story publicada em 1879. O prêmio vendeu caixas por anos justamente porque a prova de impossibilidade estava impressa numa revista acadêmica e o anúncio estava no jornal da esquina.

A conta vale muito além da caixinha de madeira. Ela responde qualquer pergunta do tipo "dá para sair daqui e chegar ali com esses movimentos": cubo mágico embaralhado à mão com uma peça remontada errada, dança de cadeiras numeradas, permutação de arquivos que só troca dois de cada vez.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de a solução aparecer, e o placar zera no dia em que você espia fora da hora. Um placar sem plateia ninguém falsifica.

Uma sequência de deslizes prova que a posição é alcançável, e nada mais. A soma das paridades decide os dois casos com a mesma conta: quando o tabuleiro tem jeito, ela confirma antes do primeiro empurrão; quando não tem, ela devolve as suas tardes.

"Quantas horas você já gastou tentando algo que uma conta de dois minutos teria descartado?"

Teste hoje, em cinco minutos: pegue um quebra-cabeça deslizante de nove peças no celular, embaralhe, some as trocas necessárias com as casas que faltam para o vazio voltar ao canto, e anote se deu par ou ímpar antes de mexer. Repita cinco vezes. As cinco previsões batem com o que acontece na tela, sem exceção.