Aldeia Numaboa UM PORTAL DIFERENTE EM PORTUGUÊS DO BRASIL

Explicando o enigma das cores

Detalhes

Categoria: Ranking / Explicações

Atualização: Quarta, 22 Abril 2009 11:55

Autor: vovó Vicki

Acessos: 19511

Certo dia, enquanto observava seu filho brincar com blocos coloridos, o matemático escocês C. Dudley Langford percebeu que aquela brincadeira também poderia entretê-lo. Contemplando a fila de blocos (ilustração a seguir) que a criança formara, Langford descobriu algo que o fascinou: o número de blocos entre um par da mesma cor variava entre 1 (entre dois amarelos), 2 (entre dois azuis) e 3 (entre dois vermelhos). Como bom matemático que era, Langford tratou de trocar as cores por números correspondentes aos espaçamentos, obtendo assim 312132.

Fila de blocos montada pelo filho de Langford.

Nasceu assim o número de Langford, contendo apenas pares de inteiros (desde 1 até 3) separados entre si por um número de dígitos igual ao valor numérico do par.

Começamos esse texto com essa curiosidade histórica porque, como deve estar claro agora, os números de Langford são a chave para resolver o Enigma das Cores, publicado aqui no Almanaque da Aldeia no dia 19 de abril de 2005 e gloriosamente decifrado três dias depois pelo Rodivaldo.

O enigma era composto por 3 perguntas: a primeira mostrando 13 seqüências de blocos coloridos (cada seqüência com 14 blocos de 7 cores distintas) e perguntando o que havia de comum entre elas; a segunda solicitando a construção de mais 13 seqüências independentes respeitando a mesma lei de formação da primeira e, a última, envolvendo decifrar um criptograma composto por vários números de 14 algarismos variando entre 1 e 7.

Como o criptanalista vencedor desse enigma, inicialmente, não deu detalhes sobre a abordagem que usou para resolvê-lo, preparamos esse texto para esclarecer a maneira pela qual tentamos induzir a solução do criptograma da questão 3. De fato, ali estava o verdadeiro enigma, ao passo que as questões 1 e 2 representavam muito mais dicas do que desafios (pelo menos era essa a intenção).

Para começar, na questão 1, fazia-se necessário "encarnar o Langford" e reconhecer, como ele fez com o brinquedo do filho, a estrutura do espaçamento entre pares de mesma cor. É claro que alguns detalhes eram aqui diferentes: em vez de 6 blocos (3 pares de cada cor), escolhemos construir nosso enigma com 14 blocos (7 pares de cada cor). A razão para essa escolha aparentemente arbitrária ficará clara mais adiante.

Além dessa "sutil modificação", para facilitar as coisas (e nos assegurar de que conduziríamos os aventureiros na direção correta), nós apresentamos o problema como um exercício de reconhecimento de padrões, oferecendo 13 seqüências distintas de cores com a estrutura de Langford. O André, dois dias depois de publicado o enigma, matou essa primeira charada descrevendo a seguinte relação entre cores e números (com os números representando o número de blocos entre cada par de mesma cor)

Observando essa regra, as cores da questão 1 podiam ser trocadas por números, como mostrado abaixo:

	→ 14156742352637
	→ 15146735423627
	→ 15163745326427
	→ 17125623475364
	→ 24723645317165
	→ 26325734615147
	→ 26327435614175
	→ 27423564371516
	→ 34673245261715
	→ 36713145627425
	→ 41617435263275
	→ 46171435623725
	→ 52642753461317

Os números acima são treze dos números de Langford, compostos por pares de 1 até 7 convenientemente espaçados (vamos denotá-los por L₇).

A questão 2 pedia que outros treze L₇ fossem encontrados (sem contar os simétricos), e talvez fosse a parte mais difícil desse enigma. De fato, só há 26 possíveis - algo bastante sugestivo para cifrar um alfabeto e, portanto, o que realmente estava sendo solicitado era que se completasse a lista de números acima.

Essa, realmente, não é uma tarefa simples se você tentar solucioná-la com "papel e lápis" (mesmo que seja lápis de cor). Porém, para resolver um enigma vale tudo, e nada impedia de buscar a lista completa em alguma outra fonte ou então programar um computador para fazer o trabalho pesado para você.

Seja como for, a tabela abaixo mostra os 26 possíveis L₇. Como os simétricos também são números de Langford, há uma certa ambigüidade sobre como fazer a apresentação. No nosso caso, removemos esta ambigüidade escolhendo apresentar os menores L₇, ou seja, entre um número e seu simétrico, apresentamos o menor.

Na coluna da esquerda, repetimos os treze L₇ da questão 1 e, na direita, listamos os que estavam faltando.

Fica aqui expresso nosso agradecimento a John Miller por gentilmente compartilhar conosco a relação dos vinte e seis L₇ (e dos cento e cinqüenta L₈), originalmente obtidos por ele em 1967.

Finalmente, depois de ter esse "alfabeto de 26 números" nas mãos, nossos criptoanalistas finalmente encaravam o criptograma da questão 3. Talvez, nessa altura, surpresos percebessem que todos números que lá estão aparecem no lado esquerdo da tabela anterior (na forma direta ou simétrica) e, possivelmente, por um instante se sentissem enganados tendo sido forçados a "desnecessariamente" encontrar tantos outros para resolver a questão 2.

Esse mal estar passaria assim que compreendessem que cada letra do alfabeto ocidental era cifrada por um L₇ (o que corresponde a dizer que cada linha do criptograma é uma letra) e, portanto, fazia-se necessário ordenar corretamente todos eles para atribuir-lhes valores literais adequados.

Falando em ordenar, nada mais natural do que começar tentando com a "ordem crescente" e, exatamente porque essa é a opção correta, é que era necessário conhecer todos L₇ - simplesmente para saber qual posição ocupam na lista ordenada os números do nosso criptograma.

A solução segue abaixo, com destaque para aqueles que, na forma direta ou simétrica, ocorrem no criptograma.

A tentativa de atribuir as letras do alfabeto aos menores números de Langford na ordem crescente, levava à bem sucedida substituição do criptograma por

(escrito na vertical), como corretamente apontado pelo Rodivaldo no dia 22 de abril de 2005, às 23 horas 10 minutos e 41 segundos.

Embora o Rodivaldo não tenha se pronunciado quanto ao método usado para decifrar, acreditamos que ele tenha seguido (pelo menos aproximadamente) os passos descritos nesse texto. Abordagens alternativas como análise de freqüência ficam dificultadas dado o pequeno tamanho do texto (e também porque cada letra podia ser cifrada por um certo número de Langford ou pelo seu simétrico, o que traz o caráter homofônico a nossa cifra).
Observação da vovó: o Rodivaldo explicou sua solução ANTES que eu publicasse este texto dos autores do enigma.

Parabenizamos o Rodivaldo por ter decifrado o enigma e o André pela contribuição parcial resolvendo a primeira questão. Além disso, agradecemos a participação de todos os outros que se interessaram, e especialmente à vovó Vicki que vem cedendo este fantástico espaço da Aldeia NumaBoa - O Almanaque (antiga Confraria do Segredo), para que possamos expor nossos desafios. Obrigado a todos!

Finalmente, a quem possa interessar, listamos algumas informações interessantes sobre os números de Langford, bem como duas referências que podem trazer maiores informações ao leitor interessado.

• Só existe um L₃, o descoberto pelo Langford (filho): 312132. De fato, durante aquela mesma famosa brincadeira, Langford (pai) acrescentou mais um par de blocos coloridos e descobriu também o único L₄ existente: 41312432.
• Números com essa estrutura não ocorrem para qualquer quantidade de pares coloridos. É possível mostrar que números de Langford só podem ser obtidos quando se utilizam quantidades de cores da seqüência 3,4,7,8,11,12,... ou seja, múltiplos de 4 ou múltiplos de 4 menos 1!
• À medida que o número de cores aumenta, aumenta também o número de construções possíveis, conforme mostrado na tabela abaixo
  

  Possíveis 'n' para formação de Ln	Quantidades de Ln Sloane A014552
  3	1
  4	1
  7	26
  8	150
  11	17792
  12	108144

• Não se sabe muito sobre possíveis aplicações para as séries de Langford (será que elas servem pra algo além de fazer enigmas?). Mesmo matematicamente falando, sua estrutura é basicamente desconhecida e até hoje a busca por esses números tem que ser feita através de força bruta (isto é, deixando o computador procurar).
• Há extensões naturais como, em vez de considerar pares da mesma cor, considerar tríades, quartetos, quintetos, etc... e impor que a distância entre eles continue obedecendo a mesma regra. Como exemplo, veja o seguinte número:
  3 4 7 9 3 6 4 8 3 5 7 4 6 9 2 5 8 2 7 6 2 5 1 9 1 8 1

Para variar, não conseguimos achar quase nada sobre os números de Langford em português. Os websites abaixo relacionados são de língua inglesa e contém muita informação interessante:

• Website de John Miller, personagem importante na solução do problema de Langford. Praticamente tudo o que se encontra na Internet sobre esses números é copiado ou adaptado deste site, portanto vale a pena dar uma olhada! O autor disponibilizou uma bibliografia aparentemente bastante rica sobre o tema, mas infelizmente composta por quase nenhum artigo disponível na internet.
• Entrada sobre o Problema de Langford na famosa enciclopédia matemática on line MathWorld do Wolfram. O texto é sucinto, objetivo e claro, ideal para uma introdução rápida ao tema.

Então é isso, um abraço a todos e até o próximo enigma!

Paulo e Suely.