Explicando o enigma P&S
|
Sab 9 Abr 2005 04:51 |
- Detalhes
- Categoria: Ranking / Explicações
- Atualização: Terça, 10 Março 2009 18:26
- Autor: Paulo e Suely
- Acessos: 15425
O enigma P&S, como chamado originalmente pela vovó Vicki, foi publicado na Confraria do Segredo no dia 29 de março de 2005 e, por 10 dias, desafiou uma enormidade de "criptoanalistas de plantão" que buscavam descobrir o que se escondia por trás da sucessão ininteligível de números e letras
A1C6D2B8G1-E1C7G3G7-B5B4H7F5A3-C5-A1E5D3G8B4C3D7D5A5-C7G7-D7G1A2A5G4E8C7G7
A1G1F1C7-H4E1A5-G8C5C3-E1A7G2-A6A5A1D2G7-G7C5A1H7B4F5G1G7
G7E5A2-C7-B7G1A1C5-B1D2H6F5E8A5
C5-G8D2-B5B4H7F2H6D3G8G1-G7D2E1-D4B1F5C5E8D2G7F6B4-D7D2D5A5-H7C5G7D7A3G7G8G1
B5A3B3E8D2-E5H4-F5D2H7E8G3G6B4G2-D6H4C5-A2H1B4-C2C5E8B4G7
G8H7E5H6F7D2G7F5C5-G1-A1E6C7G4D2
Para tanto, esses aventureiros contavam com a única dica de que "a melhor mágica que um cavalo já fez" levaria a solução do problema. A competição começou com o inevitável debate: que cavalo é esse?
Essa primeira etapa foi solucionada no dia 07 de abril, quando um visitante anônimo anunciou que o cavalo devia ser o do jogo de xadrez, já que uma análise atenta da mensagem cifrada mostrava que as letras variavam entre A e H e os números entre 1 e 8, o que corresponde às bem conhecidas "coordenadas do xadrez".
Resolvida essa primeira parte do mistério, não demorou muito até que a solução final começasse a se esboçar. No começo do dia 08 de abril, outro visitante anônimo sugeriu que a magia estaria relacionada ao fato de fazer o cavalo andar (saltando em L’s, como usual) pelas 64 casa do tabuleiro sem passar duas vezes pelo mesmo lugar, um problema que é conhecido como "knight’s tour".
A partir daí, já parecia estar claro para alguns competidores que o passeio do cavalo pelo tabuleiro numerava progressivamente as casas. Para decifrar a mensagem bastaria trocar os números assim gerados por letras, possivelmente segundo a ordem padrão 1→ A, 2→ B, ... , 26→ Z e como o tabuleiro tem mais do que 26 casas, quando a casa 27 era atingida um novo ciclo alfabético iniciava-se: 27→ A, 28→ B, ..., 52→ Z, e finalmente mais um ciclo incompleto com 53 → A, 54 → B, ..., 64→ L.
De qualquer forma, existem muitos "knight’s tours", portanto várias maneiras diferentes de realizar esta numeração. Frente a esse impasse, um outro visitante anônimo solicitou uma dica extra que lhe indicasse a opção correta. Na verdade essa escolha já estava determinada pelo enunciado do enigma: estávamos procurando pela melhor mágica.
Alguns "tours" de cavalos são especiais pois os números que eles deixam sobre as casas formam quadrados semi-mágicos. Um quadrado mágico é um conjunto de números naturais consecutivos (1,2,3,...,n2) cuidadosamente arranjados sobre uma matriz quadrada para que soma dos números de cada linha, coluna e diagonais (somente a principal e a secundária) resulte no mesmo valor (a constante mágica). Por exemplo, um quadrado mágico famoso é
Para o desapontamento de muitos, foi provado recentemente a impossibilidade de se obter quadrados mágicos com o "tour" de cavalos. Todavia, exigindo-se obter o mesmo resultado apenas na soma das linhas e colunas (deixando-se as diagonais livres), é possível encontrar uma variedade de trajetórias distintas! Quadrados assim são chamados de semi-mágicos, por isso o "tour" de um cavalo no tabuleiro padrão é, na melhor das hipóteses, semi-mágico...
Naturalmente vem a pergunta: qual é o "tour" dos cavalos que leva ao quadrado mais aproximadamente mágico? (aquele em que a soma das diagonais fica tão próxima quanto possível da soma comum das linhas e colunas). Esse "tour" é certamente a melhor mágica que um cavalo já fez e foi descoberto em 1882 por Francony. Nele, a soma de todas as linhas e colunas dá 260 (que é a constante mágica para todo quadrado mágico 8 x 8, seja ele criado pelo movimento dos cavalos ou por qualquer outra coisa) e a soma das diagonais dá 264 e 256, ou seja, um desvio de apenas 4 da constante mágica!
Agora, com vocês, o mais mágico "tour" de cavalo
O Sr Pilha, no dia 09 de abril, precisamente às 9hs 12 min e 31s publicou o texto claro do enigma e explicou que ele o obteve após usar a numeração acima.
Para quem não entendeu a explicação curta (mas absolutamente correta) do Sr Pilha, aqui vão mais alguns detalhes.
O que ele fez foi transformar os números em letras segundo a prescrição mais natural (já discutida anteriormente), obtendo o seguinte mapa entre as coordenadas do xadrez e as letras do alfabeto
A partir daí foi só trocar as coordenadas do texto pelas letras correspondentes e se emocionar ao ver o belo trecho do poema "Procura da Poesia", de Carlos Drummond de Andrade, se revelar diante de seus olhos!
De acordo com o próprio Sr Pilha, o texto claro é
CHEGA-MAIS-PERTO-E-CONTEMPLA-AS-PALAVRAS
CADA-UMA-TEM-MIL-FACES-SECRETAS
SOL-A-FACE-NEUTRA
E-TE-PERGUNTA-SEM-INTERESSE-PELA-RESPOSTA
POBRE-OU-TERRIVEL-QUE-LHE-DERES
TROUXESTE-A-CHAVE
Com relação a isso, nós devemos assumir um pequeno deslize no processo de encriptação. Na primeira palavra da terceira linha, acidentalmente trocamos um B por um L, transformando o que deveria ser a palavra SOB na palavra SOL... Nossas mais sinceras desculpas por esse engano.
Mesmo assim, ficamos profundamente orgulhosos do nosso enigma ter resistido todo esse tempo, mesmo sob o fogo cerrado de tantos competidores (até a solução, o contador da Confraria registrava mais de 600 visitas ao enigma!). Ficamos mais ainda realizados porque a descoberta do texto claro se deu da forma mais elegante possível, isto é, o Sr Pilha descobriu a maneira que ciframos e aplicou-a ao contrário para decifrar. Na criptoanálise, isso nem sempre é feito assim. Muitas vezes uma mensagem é decifrada sem que se descubra a forma pela qual ela foi cifrada. Uma ferramenta muito comum e poderosa nesse sentido é a análise de freqüência dos códigos do criptograma.
Um dos nossos objetivos com esse enigma era propor um desafio resistente a esse tipo de análise. De fato, havendo mais de um código para uma mesma letra (por exemplo, a letra A é cifrada por 3 códigos distintos: C7, G1 e A5), a análise de freqüência fica dificultada. Cifras assim são conhecidas como "substituições homofônicas" (você pode aprender muito sobre essas substituições aqui na Aldeia que mostra a Cifra de Babou).
Finalmente, quanto ao problema dos "tours dos cavalos", a Internet está repleta de informações (na maioria em websites de língua inglesa). Alguns particularmente interessantes na nossa opinião são
- [1] http://www.ktn.freeuk.com/sitemap.htm
Do autor George Jelliss. Certamente um dos mais completos websites sobre "tours" de cavalos (semi-mágicos ou não). Contém informação histórica interessante sobre o problema e também desenvolvimentos recentes (alguns deles devidos ao próprio autor). Escrito por uma autoridade no assunto. - [2] http://magictour.free.fr/
O website do projeto de busca por "tours" mágicos de cavalos. O projeto foi concluído em 5 de agosto de 2003 com o resultado negativo: cavalos não fazem quadrados mágicos num tabuleiro 8 x 8. Porém, como resultados positivos, vários outros "tours" semi-mágicos foram encontrados. - [3] http://mathworld.wolfram.com/news/2003-08-06/magictours/
Um artigo de Eric W. Weisstein sobre a prova da impossibilidade de "tours" mágicos de cavalos nos tabuleiros 8 x 8. - [4] http://mathworld.wolfram.com/MagicTour.html
Um resumo da ópera atual sobre "tours" mágicos de forma geral. Mostra inclusive um "tour" mágico de reis no tabuleiro 8 x 8. - [5] http://www.chessbase.com/columns/column.asp?pid=163
Excelente artigo de Frederic Friedel, repleto de estórias, informações interessantes e dicas de como fazer "tours" de cavalos, também aponta para ótimos links onde é possível praticar o "tour"! - [6] http://www.worle.com/chess/index.html
Gaste primeiro um bom tempo nessa simulação tentando construir um "tour" de cavalos, quando você cansar de encurralar seu cavalo, clique no link Warnsdorff’s rule para aprender uma forma prática de fazer!
OBS: enquanto estiver consultando esses websites, mantenha em mente que alguns deles chamam de "tours" mágicos o que nós chamamos de "tours" semi-mágicos, e de "tours" diagonalmente mágicos aqueles que nós chamamos de "tours" mágicos.
Consultando esses websites encontramos as seguintes informações que merecem destaque
- Note que o "tour" de Francony, além de ser o mais mágico, é também fechado ou re-entrante (ou seja, o cavalo termina o "tour" a um movimento de voltar para a posição inicial!)
- Curiosamente, é comum encontrar um outro "tour" gozando do status de "mais aproximadamente mágico" para os cavalos (most magic knight’s "tour"). Neste, as diagonais somam 348 e 168. Para nós, os autores do enigma, o significado de ser mais aproximadamente mágico é ter a soma das diagonais mais próximas de 260, e portanto o "tour" de Francony é notavelmente melhor do que este outro. Essa também parece ser a opinião do autor do website [4].
- A estimativa da quantidade de "tours" de cavalos possíveis é de 13.267.364.410.532 (McKay, 1997). Desses, apenas 140 são semi-mágicos, e nenhum é mágico!
- A dúvida sobre a existência de "tours" mágicos de cavalos é um problema matemático que esperou 150 anos pela solução. O resultado negativo de 2003 foi obtido através de uma busca computacional de 138,25 dias a 1GHz.
Agradecemos muito pelo interesse de todos os competidores e parabenizamos todos pelas contribuições. Embora o grande vencedor tenha sido o Sr. Pilha, estamos certos de que as contribuições parciais de cada um dos visitantes anônimos foram de grande valia para o desfecho dessa empreitada.
Vemos vocês no próximo enigma (já estamos pensando nele!!)
Paulo e Suely