|
|
A torre de 64 discos que ninguém vai terminar
Um professor francês vendeu o quebra-cabeça sob nome falso em 1883, e a versão lendária dele pede mais de 18 quintilhões de jogadas.
|
Três hastes e uma torre de discos empilhados
|
| ▼ |
| |
|
Em 1883 apareceu nas lojas de Paris uma caixa de madeira com três hastes fincadas numa base. Numa delas, uma pilha de discos de tamanhos diferentes, o maior embaixo e o menor no topo. As outras duas hastes vinham vazias, e o comprador tinha que descobrir sozinho o que fazer com elas.
O rótulo creditava a invenção a N. Claus de Siam, mandarim do colégio de Li Sou Stian. Não existia mandarim nenhum, não existia colégio nenhum, e Siam entrou ali só para dar sotaque de Oriente ao brinquedo.
N. Claus de Siam é um anagrama de Lucas d'Amiens, e Édouard Lucas era professor de matemática num liceu de Paris, nascido em Amiens. O mesmo homem que passava o dia com números primos assinou o brinquedo com as próprias letras embaralhadas, e ninguém percebeu na hora.
As regras cabem em duas linhas. Move-se um disco por vez, sempre do topo de uma haste para o topo de outra, e um disco maior nunca pode pousar sobre um disco menor.
Junto com a caixa vinha uma história. Num templo de Benares, sob a cúpula que marca o centro do mundo, brâmanes transportariam sem descanso uma torre de sessenta e quatro discos de ouro entre três agulhas de diamante, e no instante da última jogada o templo viraria pó e o mundo acabaria com ele.
A lenda foi escrita para vender caixa de madeira, mas a conta que ela esconde é verdadeira e é assustadora. A torre de sessenta e quatro discos exige mais de dezoito quintilhões de jogadas, e uma jogada por segundo, sem pausa desde o começo do universo, ainda estaria longe do fim.
O que impressiona não é o tamanho do número. É o contraste entre a regra, que qualquer criança entende em dez segundos, e o custo, que nenhuma civilização paga.
Guarde essa distância entre uma regra curta e um custo que explode. Ela é o eixo do enigma de hoje e também da conta que ficou pendente na sala de festa, com vinte e três convidados e uma aposta na coincidência de datas que quase ninguém aceita de primeira.
Continue lendo ↓
|
|
|
|
I A resposta de ontem
Duzentos e cinquenta e três pares numa sala só
|
|
A pergunta era simples: numa sala com vinte e três pessoas, qual a chance de pelo menos duas fazerem aniversário no mesmo dia do ano. A resposta é 50,7 por cento, e a aposta na coincidência paga um pouco melhor que a aposta na ausência dela.
O erro de intuição nasce na hora de escolher o que contar. A cabeça conta convidados, olha para trezentos e sessenta e cinco dias de calendário e conclui que vinte e três é pouco demais para cobrir tanto espaço.
A sala não tem vinte e três chances de repetir uma data. Ela tem duzentos e cinquenta e três pares de pessoas, e basta um único par fechar para a aposta ser ganha.
O número de pares cresce com o quadrado do tamanho do grupo, não com o tamanho do grupo. Dobrar a lista de convidados quadruplica as tentativas, e é por isso que a sala fica pequena tão rápido.
Veja a distância entre contar gente e contar pares:
| 10 pessoas | 45 pares |
| 23 pessoas | 253 pares |
| 41 pessoas | 820 pares |
| 57 pessoas | 1.596 pares |
O caminho mais curto até a resposta é calcular o contrário. Em vez de somar todas as formas de haver coincidência, calcule a chance de todas as datas serem diferentes e subtraia de um.
A segunda pessoa encontra 364 dias livres em 365. A terceira encontra 363, a quarta encontra 362, e o produto dessas frações encolhendo juntas desce abaixo de metade exatamente na vigésima terceira pessoa.
Existe um teste limpo para separar quem entendeu de quem decorou o número. Se a sua explicação também serve para a versão em que você fixa uma data antes de a sala se formar, ela ainda não é a explicação certa.
Essa outra versão, a pessoal, precisa de mais de duzentas pessoas para passar de metade. A diferença inteira está em quem é o sujeito da frase: um convidado específico ou qualquer par que se forme.
Guarde esse hábito de perguntar o que exatamente está sendo contado, porque ele reaparece agora numa haste de madeira. Contar discos e contar jogadas são coisas diferentes, e a segunda cresce de um jeito que a primeira não deixa adivinhar.
|
|
|
|
|
II O Enigma do dia
O custo escondido de uma regra de duas linhas
|
|
Três hastes, uma torre de discos de tamanhos diferentes empilhada na primeira, e a missão de reconstruí-la inteira na terceira. Move-se um disco por vez, e um disco maior nunca pousa sobre um disco menor. Qual é o número mínimo de jogadas para uma torre de sessenta e quatro discos, e por que ele é tão grande?
|
A pergunta é sobre o mínimo, não sobre um caminho qualquer. Existem infinitas maneiras de embaralhar discos entre hastes sem chegar a lugar nenhum, e o que interessa é o menor número de jogadas que resolve.
Comece pelo caso menor que ainda tem graça. Com um disco, uma jogada resolve. Com dois discos, três jogadas resolvem, e a estrutura dessas três já contém tudo que acontece depois.
Para levar o disco maior de uma torre até a haste de destino, a haste precisa estar vazia e o disco maior precisa estar sozinho. Ou seja, tudo que estava em cima dele já foi parar na haste do meio, inteiro e empilhado na ordem certa.
Fora da regra: girar a base, tirar dois discos de uma vez, deixar um disco fora das hastes enquanto pensa, ou desistir do mínimo e aceitar qualquer solução que funcione.
Onde quase todo mundo trava
A reação imediata é imaginar que dobrar o número de discos dobra o trabalho. Sessenta e quatro discos pareceriam então algo como o dobro de trinta e dois, e o total soaria grande sem ser absurdo.
A segunda reação, mais teimosa, aceita que o crescimento é rápido, mas continua tratando o problema como uma soma. Ela pensa em acrescentar jogadas a cada disco novo, quando o que acontece é outra coisa.
|
Cada disco novo não acrescenta jogadas, ele repete todo o trabalho anterior mais uma vez e ainda cobra uma jogada extra para o próprio disco. O custo de uma torre é sempre o dobro do custo da torre anterior, mais um.
|
A frase acima é a solução inteira. Para mover uma torre de n discos, você move n menos um discos para a haste auxiliar, move o disco de baixo para o destino, e move de novo a torre de n menos um por cima dele.
A escada de jogadas fica assim:
| 3 discos | 7 jogadas |
| 5 discos | 31 jogadas |
| 10 discos | 1.023 jogadas |
| 20 discos | 1.048.575 jogadas |
| 64 discos | 18.446.744.073.709.551.615 jogadas |
O salto entre vinte e sessenta e quatro é onde a intuição desmonta de vez. Quarenta e quatro discos de madeira a mais, uma pilha que ainda cabe na palma da mão, e o trabalho sai de um milhão para dezoito quintilhões.
A pergunta continua de pé e ela é sobre o mecanismo, não sobre o número final. Explique por que resolver a torre grande obriga a resolver a torre menor duas vezes, e por que não existe atalho que economize uma dessas duas passagens.
|
|
|
|
|
III Sequência
Cinco moedas e três círculos no papel
|
|
O experimento dispensa a caixa de madeira do brinquedo. Você precisa de cinco moedas de valores diferentes e de uma folha de papel com três círculos desenhados lado a lado.
Empilhe as cinco moedas no círculo da esquerda, a maior embaixo e a menor no topo. A regra na mesa é a mesma da haste: uma moeda por vez, e nunca uma moeda maior sobre uma menor.
1. Resolva primeiro com três moedas e conte as jogadas em voz alta. Anote o total no papel antes de tentar a versão maior, porque o número precisa estar escrito para o padrão aparecer.
2. Refaça com quatro moedas e depois com cinco, sempre anotando o total ao lado do anterior. Não procure a fórmula, procure a relação entre uma linha e a linha de cima.
3. Compare a coluna de totais com a coluna de moedas. Cada linha nova vale o dobro da anterior mais um, e é essa relação que transporta a mesa de jantar direto para os sessenta e quatro discos do templo.
|
"Os brâmanes se revezam noite e dia transportando os discos de uma agulha para outra, e quando o último disco tiver mudado de lugar a torre e os templos desabarão, e o mundo desaparecerá num trovão."
Henri de Parville, La Nature, revista de ciência popular, Paris, 1884.
|
A frase acima é a lenda como ela circulou na imprensa francesa, um ano depois de o brinquedo chegar às lojas. O templo nunca existiu, a agulha de diamante nunca existiu, e a única coisa verdadeira na história é a aritmética que ela embrulha.
Se travar no raciocínio, reduza o problema em vez de ampliá-lo. Pergunte o que precisa estar verdadeiro no instante anterior ao disco de baixo se mover, e você vai encontrar a torre menor já inteira na haste do meio.
A Sequência é o placar de quem vira a chave sozinho. Um ponto por enigma fechado antes de a solução aparecer, e o placar zera no dia em que você espia fora da hora. Ninguém confere, e um placar sem plateia é o único que não se falsifica.
Um último aviso de jogo limpo. Se a sua explicação depende de decorar a fórmula, ela não conta: a prova é conseguir dizer, sem papel, por que a torre de vinte discos custa exatamente o dobro da torre de dezenove mais uma jogada.
Uma regra que cabe em duas linhas pode esconder um custo que nenhuma civilização paga. O brinquedo de madeira e a torre de ouro são o mesmo problema, e a única diferença entre eles é quantas vezes o trabalho se repete dentro de si mesmo.
"Quanto tempo você aguentaria mover discos sabendo que o fim não chega?"
|
|
|
|
Guia Enigma do Dia · Novo
O Silêncio na Mesa
O Protocolo de 4 Tempos pra soltar uma charada e travar a conversa inteira.
|
|
| |
|
Quiz da edição
|
|
Segundo o texto, qual é o número mínimo de jogadas para resolver a torre de 64 discos?
| | |
