Maps

sexta-feira, 25 de maio de 2007

O Jogo da Vida


Gostaria de apresentar o viciante e pouco conhecido "Jogo da Vida". Empresários, cuidado! O Jogo da Vida pode parar um departamento inteiro durante toda a tarde de forma mais eficiente do que o Orkut. Sob sua aparência ingênua e trivial se esconde um voraz devorador de cérebros.

Deixando a brincadeira de lado, o Jogo da Vida (Game of Life) foi inventado pelo matemático inglês e professor da Universidade de Princeton John Horton Conway em 1970 e desde lá tem despertado nossa curiosidade e imaginação. Ele não é propriamente um jogo no sentido clássico, não há objetivo, não há jogadores, vencedores ou perdedores. Definida uma posição inicial para as peças do jogo (células) , regras simples determinarão os acontecimentos que estão por vir. O Jogo da Vida é surpreendente em muitos aspectos, com várias facetas e desdobramentos, um ambiente muito rico para novas descobertas.

O Jogo da Vida é composto de um grande tabuleiro infinito, inteiramente quadriculado onde cada um dos quadradinhos representa uma célula que poderá estar viva ou morta. Inicialmente todas as células estarão mortas, no ponto em que nós, em nossas raras intervenções (na verdade a única), iremos definitivamente criar vida e compor o que chamamos de padrão inicial (ou configuração inicial). A seguir, comandamos uma espécie de Big Bang, isto é, damos início ao jogo e observamos seu comportamento. Conway definiu cuidadosamente 3 simples regras que irão reger o comportamento do jogo, uma regra para os nascimentos, outra para a morte e outra para a sobrevivência:

  • Regra para nascimento: Toda célula morta se tornará viva quando exatamente 3 de suas 8 células vizinhas estiverem vivas.
  • Regra para sobrevivência: Toda célula viva que possui 2 ou 3 células vizinhas vivas, continuará viva.
  • Regra para morte: Em todos os outros casos, uma célula morrerá (ou permanecerá morta), ou por solidão (1 ou menos vizinhos vivos) ou por lotação (4 ou mais vizinhos vivos).

Apesar de simples, estas regras costuma gerar alguma confusão. As pessoas normalmente perguntam: "Mas o que devo fazer primeiro? Eliminar as células mortas ou incluir as que irão nascer?". A resposta é nenhum nem outro! As duas operações deverão ser feitas ao mesmo tempo. Dito de outra maneira, é irrelevante a ordem em que as operações são feitas, o resultado é sempre o mesmo. Um dica é marcar as que vão nascer e as que irão morrem sem alterar o estado do jogo, depois disso pode-se de fato criar as células maracadas para nascer e apagar aquelas marcadas para morrer. Certifique-se que você compreendeu esta sutilieza acompanhando o exemplo abaixo.

Suponha a execução do Jogo da Vida a partir de um padrão inicial composto de 5 células vivas enfileiradas. Esse tipo de padrão é conhecido como pentaminó, isto é, um padrão formado por cinco quadradinhos onde cada uma delas compartilha no mínimo uma face com qualquer um dos outros. O pentaminó é, enfim, uma generalização do dominó, porém com cinco quadradinhos ao invés de dois.

Quando submetemos este padrão às regras, ele se transformará no oitavo desenho sete passos após o Big Bang. Depois disso, surpreendentemente, o nono padrão será exatamente igual ao sétimo que por sua vez gera novamente o oitavo, resultando finalmente num padrão oscilante depois de 7 gerações.




Nem sempre o padrão inicial resulta em um padrão oscilante. Em muitos casos a população inicial caminha para sua total extinção, onde depois de algum tempo todas as células estão novamente mortas. É o que ocorre com este outro pentaminó, extinto em apenas 3 passos (ou gerações).
Ao conceber seu jogo, Conway testou todos os 12 pentaminós existentes e logo percebeu que ou eles se tornavam oscilantes, ou eram extintos. Havia, porém uma única exceção, um dos pentaminós (abaixo) se recusava a estabilizar depois de um número significativo de passos. Lembrem-se vocês leitores que Conway testou estes padrões em um tabuleiro ou em um papel milimetrado, afinal eram os anos 70 e os computadores não eram assim tão disponíveis, mesmo para acadêmicos de porte.


Felizmente, preparei uma surpresa para vocês, aqui mesmo neste blog. Basta rolar a página até o final que vocês verão um simulador do Jogo da Vida que desenvolvi para testarmos quantos padrões desejarmos. Ele foi desenvolvido em Java e só irá funcionar se o plug-in do Java estiver devidamente instalado no browser de vocês, se não for esse o caso basta entrar no site http://www.java.com/pt_BR/ e clicar numa seta amarela enorme que aparece logo de cara que a atualização será efetuada. É de graça!.

Para criar vida, basta clicar em qualquer quadradinho que eles viverão, tornando-se pretos. Um novo clique, e eles morrerão novamente. Uma vez definida a posição desejada, basta clicar no botão ON em cima à esquerda. Se desejarem pausar a simulação cliquem novamente neste botão que agora tem o nome de OFF.

Vocês logo perceberão que um intuitivo seletor de velocidade fica à direita deste botão e pode ser usado à vontade. As duas informações que ficam em cima e à direita são respectivamente, o número de células vivas e a quantidade de gerações (passos) realizados. Finalmente, na parte inferior há uma versão do mesmo universo, porém reduzido de maneira que possamos visualizar a ação de uma perspectiva mais ampla. É possível arrastar o retângulo vermelho posicionado no centro desta região para selecionar áreas distantes deste mesmo universo. Experimente!

Bom, por hora não vou estragar a surpresa de vocês. Há ainda muito o que dizer mas vou deixar vocês se divertirem um pouco...




quinta-feira, 17 de maio de 2007

The Long Tail


Não resisti, forças misteriosas forçaram-me a investigar um pouquinho mais a natureza do número 9376, este número estranho de caráter auto-reprodutivo que quando multiplica-mo-lo (gostaram da mesóclise? Corrijam-me se a usei errado) por ele mesmo resulta em um novo número com o mesmo "código genético".

Encarei ele de frente e algo novo surgiu. Qualquer "cauda" do número 9376 também é auto-reprodutiva! Ok, vocês não endenderam nada, afinal o que é a "cauda" de um número? Bom, foi o nome que encontrei para designar o número encontrado em qualquer trecho à direita do número original. Assim, 9376 tem 4 caudas, o número 6, o número 76, o número 376 e ele próprio, o número 9376. Fazendo as contas, logo vi que as 4 caudas de 9376 também são auto-reprodutivas:

9376 x 9376 =
87909376
376 x 376
=
141376
76 x 76
=
5776
6 x 6
=
36

Pensei um longo tempo neste assunto e percebi que este fato é necessário para que o número seja auto-reprodutivo, ou seja: todas as caudas de um número auto-reprodutivo deverão ser necessariamente números auto-reprodutivos. É simples demonstrar este resultado e sugiro que vocês tentem, não envolve nada além do que vocês aprenderam até a sétima série. Para aqueles de menor magnetismo pessoal aconselho apresentar este resultado num sábado a noite qualquer. Vocês verão o sucesso que irão fazer ! É melhor do que carro importado.

Neste ponto, um sentimento megalomaníaco apareceu em meu peito. Será que eu não poderia construir números auto-reprodutivos maiores, com digamos mil dígitos, ou dez mil, talvez 1 milhão? Lá fui eu para o caderno de alemão de minha esposa rabiscar e rabiscar durante horas. Depois de uma eternidade finalmente eu desisti frustrado. O que eu estava procurando era uma regra para encontrar um número reprodutivo a partir de uma de suas caudas. Por exemplo, gostaria de, a partir de, digamos 76, encontrar 376 ou 9376. É claro, esta regra deveria ser suficientemente poderosa para eu encontrar números reprodutivos maiores do que 9376.

Como não podia deixar de ser sofri uma reprimenda da minha esposa. Onde já se viu, disse ela, estragar todo o meu caderno com esses rabiscos? (sim, ela os chamou de rabiscos toda a minha arte). Abalado e com um caderno novinho e sem pautas que ganhei dela, resolvi apelar, fazer uso de um arsenal matemático bem além da sétima série. Com caderno novo, técnica nova e esposa trabalhando fora, pude me deliciar com o melhor que a internet pode oferecer... é claro, dicas sobre a aritmética modular.

Esse relato tinha tudo para acabar aqui, mas contrariando todas as probabilidades eu encontrei a tal regra que gera números auto-reprodutivo cada vez maiores. Ela é simples e bela, quase uma pintura. Aprecie:

3n2-2n3 (mod 102d(n))

onde n é um número auto-reprodutivo e d(n) é o número de dígitos deste número. O resultado da expressão acima é um novo número auto-reprodutivo com o dobro de dígitos do anterior. Calma, não é motivo para pânico, posso reescrever a fórmula acima sem usar a palavra "mod". De fato, a expressão é equivalente a:

Resto da divisão de 3n2-2n3 por 102d(n)

Além de produzir um número auto-reprodutivo maior do que o número utilizado (que chamarei de "semente") a demonstração da fórmula acima trouxe uma informação muito mais sutil e importante. Existem infinitos números auto-reprodutivos, afinal, sempre será possível construir um maior a partir da "semente" anterior.

Para os que tentarem fazer as contas com uma calculadora simples tenho dois avisos: primeiro, vocês não irão muito longe pois como o tamanho dos números dobra a cada iteração, logo o limite de suas calculadoras irá estourar; segundo, é necessário saber como calcular "restos de divisão" quando o dividendo é negativo. No meu caso, preferi não perder muito tempo e lancei mão de recursos computacionais mais poderosos. Enfim, a partir do número 6 como "semente", obtive a uma boa sequência de números auto-reprodutivos, cada um com tamanho duas vezes maior do que o anterior.

6
76
9376
87109376
3740081787109376
95893380022607743740081787109376

Observe o poder do algoritmo, com apenas 5 iterações obtive, não 5 como pode parecer a primeira vista, mas 32 números auto-reprodutivos. Basta pegar o maior deles e listar todas as suas caudas. E para isso foi necessário partir de uma semente minúscula que é o número 6, que é claro, é um número auto-reprodutivo.

6
76
376
9376
09376
109376
7109376
87109376
787109376
1787109376
81787109376
etc...

A pergunta seguinte surgiu naturalmente, como deverá ter ocorrido para alguns de vocês (ou você... se apenas uma pessoa ler isso aqui. Oi mãe!) caros leitores. Não existe outra semente pequena diferente de 6? Uma coisa é claro, se outra semente existe, ela deverá ter apenas 1 dígito, pois o fato de ter mais do que 1 dígito implica que sua cauda de tamanho 1 também seja auto-reprodutiva. Bom, agora ficou fácil, basta testar todos os números de 1 dígito e... Voilà !!! o número 5 também é auto-reprodutivo, afinal 5 x 5 = 25. Quantos aos outros números, nenhum deles é auto-reprodutivo.

A fórmula é bem poderosa, e funciona com qualquer semente, então foi simples calcular toda um nova família de números auto-reprodutivos a partir da semente 5.

5
25
625
0625
90625
890625
2890625
12890625
212890625
8212890625
18212890625
918212890625
etc...

Incansável e motivado pela últimas realizações, fui atrás de novas regularidades e resolvi somar os números das duas famílias usando a expressão R5(d) + R6(d), onde R5(d) representa o maior número auto-reprodutivo de cauda 5 que possui d ou menos dígitos, analogamente R6(d) é o maior número auto-reprodutivo de cauda 6 que possui d ou menos dígitos. Bom, realizei a soma e obtive a tabela abaixo:


n R5(n) R6(n) R5(n)+R6(d)
1 5 6 11
2 25 76 101
3 625 376 1001
4 625 9376 10001
5 90625 9376 100001
6 890625 109376 1000001
7 2890625 7109376 10000001
8 12890625 87109376 100000001
9 212890625 787109376 1000000001
10 8212890625 1787109376 10000000001
11 18212890625 81787109376 100000000001
12 918212890625 81787109376 1000000000001
13 9918212890625 81787109376 10000000000001
14 59918212890625 40081787109376 100000000000001
15 259918212890625 740081787109376 1000000000000001
16 6259918212890625 3740081787109376 10000000000000001
17 56259918212890625 43740081787109376 100000000000000001
18 256259918212890625 743740081787109376 1000000000000000001
19 2256259918212890625 7743740081787109376 10000000000000000001


Incrível, não é mesmo? A soma entre os números reprodutivos das famílias de cauda 5 e de cauda 6 resultam sempre em um mesmo padrão, independentemente do tamanho do número, ou da cauda se preferir. A expressão que ilustra esse resultado é:

R5(d) + R6(d) = 10d + 1

Gostei muito desta conjectura e ainda me espanto com ela, dois números de famílias diferentes de números auto-reprodutivos quando somados resultam em uma família de números capicuas. Para quem não sabe, números capicuas são aqueles que lido da direita para esquerda ou da esquerda para a direita resultam sempre no mesmo número. Para os mais letrados, capicua é o equivalente numérico dos palíndromos.

Após tantas regularidades e da existência de uma família infinita de números auto-reprodutivos, desconfiei que alguém já tenha trabalhado com isso e mais uma vez recorri ao Oráculo. "Oh Oráculo. Existe alguém que descobriu os números auto-reprodutivos antes de mim?". Aguardei um pouco e obtive: "Sim, caro mortal, muitas pessoas trabalharam com isso e já haviam percebido isso há muito tempo, porém deram outro nome, chamaram de números automórficos". Bom, um pouco decepcionado, confesso, voltei a minha insignificância e escrevi este pequeno artigo.

Um último comentário é de que não encontrei no Oráculo qualquer referência à conjectura acima. Isso significa que é possível que ainda não tenha sido batizada por ninguém. Como prêmio para quem leu até aqui (viu mãe) prometo batizar a conjectura acima com o nome da pessoa que a demonstrá-la e mandar um post com a demonstração. Lembro que uma conjectura ainda não demonstrada pode se mostrar falsa para algum valor de n maior, portanto uma demonstração se faz necessária. Se a conjectura é demonstrada, ela não é mais uma conjectura e sim um Teorema.

Um abraço a todos
Alexandre

quarta-feira, 16 de maio de 2007

Fiat Lux! E Deus criou a matemática


A matemática que aprendemos na escola está incompleta. Aprendemos a matemática dos resultados, das aplicações, dos engenheiros. Magicamente as fórmulas nos são dadas, e na sequência um exercício modelo, e depois outro e outro, muito provavelmente bem parecidos. Quando nos falta a fórmula, procuramos em tabelas e livros, ou melhor em nosso Oráculo moderno, o Google, afinal tudo o que havia para ser descoberto (ou inventado) na matemática já foi feito, não é mesmo?

Não estou dizendo que o ensino desta forma está errado, afinal é assim que o mundo vem caminhando, e bem, no avanço da técnica e da tecnologia. Só o considero incompleto e falacioso. Incompleto pois não há espaço para assuntos que ofendem nosso senso de utilidade. Falacioso pois distorce a maneira de como esta ciência foi criada e desenvolvida.

Discuto muito a Ditadura da Utilidade. Quem, em uma aula de matemática, já não se pegou resmungando "Mas pra que serve isso?" ou "Não vou ganhar nada ficando nesta aula." Bom, rebato perguntando porque é que tem que servir para alguma coisa? Ou melhor, o que significa "servir" para algo? O que é mais útil, pergunto novamente, algo que nos deixa mais feliz ou algo que nos traz dinheiro?

Arrisco a dizer que a matemática não trata do "útil". Mesmo quando algum resultado "útil" aflora dela, ele "sai" do domínio da matemática para encontrar lugar em outras cearas, muitas vezes na engenharia, na física e não raro na economia e na biologia sem contar suas eventuais aventuras nas ciências sociais.

Gosto muito de citar o matemático inglês G.H. Hardy, que viveu entre 1877 e 1947. Hardy define um matemático como um criador de padrões, ou seja, estruturas ideais dotadas de espantosa permanência e que, como todas as outras criações humanas, devem poder ser avaliadas pela sua beleza e seriedade.

Há dois pontos no comentário de Hardy que faço questão de ressaltar. Primeiro, é a observação de que a matemática é uma criação humana, fato que a aproxima de todas as outras ciências. Segundo é o que Hardy chamou da espantosa permanência da matemática, o que a distancia das outras ciências. Explico, a matemática é uma ciência cumulativa onde seu corpo sofre apenas adições de conhecimento e nunca subtrações. Todas as outras ciências, inclusive a física sofreram subtrações ou alterações ao longo de sua história.

Posto que é uma criação humana, por que nos parece tão distante, tão austera e enfadonha? Porque nos ensinam assim, suponho. Neste processo de limpeza, lapidação e esterilização usualmente realizado na matemática escrita e ensinada, perdemos a ligação com seu desenvolvimento e com as pessoas que a criaram, suas vaidades, invejas e ambições. É a falácia do ensino da matemática: A forma como nos ensinam matemática não reflete a forma como ela foi desenvolvida.



sexta-feira, 4 de maio de 2007

Número 9376


Na noite de quinta passada (29/03/2007) eu estava estudando uma versão atual da antiga linguagem de programação Smalltalk, uma distribuição chamada Squeak. A arquitetura da linguagem chamou minha atenção para uma série de fatores, porém não havia ningúem para eu discutir o assunto além da Fabiana que, para quem não sabe, é minha esposa.

Algo no meu íntimo dizia que a Fabiana não se interessaria pelos meandros da linguagem, então optei por uma abordagem diferente para ver se conseguia iniciar algum diálogo sobre o assunto:

Olha Fabiana, sua calculadora consegue fazer 2 elevado a 100?
Que? Minha calculadora não tem "elevado".
Ah (suspiro)... Bom, pode ter certeza que ela não faz, pois o número é muito grande.
Sei...
Olha o que o "meu" software consegue fazer?

Neste ponto digitei o comando necessário e "voilà", lá estava o numerão equivalente a 2 elevado a 100. A Fabiana deu de ombros e fingiu estar bastante impressionada. Incentivado pelo "entusiasmo" dela, me engajei em uma cruzada pelos limites da linguagem.

Olha agora, 2 elevado a 1000 !!! e lá estava a resposta
Olha, olha, olha agora, 2 elevado a 3000 !!! eu de novo

E assim foi, a cada novo comando eu chamava a Fabiana para mostrar para ela como os números iam crescendo. 2 elevado a 5000, 6000, 7000, 8000, 10000, 15000 e 20000. Ela sempre respondia com algum comentário do tipo "Sei" ou "Que legal" ou "Nossa" até que em determinado momento sua expressão se alterou de forma que eu pude ler seu pensamento.

Já esperando por uma frase do tipo: "Você já brincou bastante, agora vamos dormir, né?" me surpreendi com o que de fato ouvi.

Faz 2 elevado a 1000 de novo ela disse.
2 elevado a 1000!? É prá já!
Hum... faz agora 2 elevado a 2000 comandou ela novamente
Aí está.
2 a 3000 agora.
Pronto.

Neste ponto o que ouvi foi ainda mais surpreendente, pelo menos para mim.

Engraçado, você reparou que os números sempre terminam com 9376

Olhei para o número, repeti as contas, e sim, de fato, os números da forma 2 elevado a múltiplos de 1000 terminavam todos como 9376. Fiquei intrigado com aquilo e recomecei os testes. Logo descobri que 2 elevado a 500 também resulta num número que termina com 9376, e também 2 elevado a 1500, 2500, 3500, etc... Enfim, conclui que o número 2 elevado a qualquer múltiplo de 500 termina com 9376.

Bom, como qualquer matemático que se preze, eu não estava satisfeito, era ainda necessário provar o que parecia ser uma lei universal. Peguei lápis e papel e comecei a rabiscar. Não repetirei a demonstração aqui, mas de fato, foi possível provar que 2 elevado a qualquer múltiplo de 500 termina sempre com 9376 teorema que, em homenagem a minha esposa, chamarei de Teorema da Fabiana.

Porém, no processo de demonstração, descobri um resultado bastante interessante, e mais fundamental do que o anterior. Descobri que qualquer número que termine com 9376 multiplicado com outro número que termine com 9376 termina com um número que termina com 9376. Observe:

9376 x 9376 = 87909376
8059376 x 129376 = 1042689829376

Este resultado explica o Teorema de Fabiana. Uma vez que 2 elevado a 500 termina com 9376, 2 elevado a 500k (com k inteiro) é igual a 2 elevado a 500 elevado a k, o que obviamente é um número que termina com 9376.

Empolgado com a descoberta de um novo resultado, desconfiei que alguém já poderia ter percebido esta curiosidade. Resolvi pesquisar um pouco no Google. Quem sabe tinha conseguido um resultado original (apesar de pequeno). As primeiras pesquisas foram promissoras, isto é, nada relacionado ao número 9376 referente ao fato recém descoberto. Insisti um pouco mais escolhi novas palavras chaves até quando usei "9376 Math curiosity" e bingo, encontrei alguém que havia percebido o fato.

A referência encontrada era um exercício do livro "Concrete Mathematica" do Donald Knuth e outros dois autores. Knuth é um gênio matemático e da ciência da computação. Foi ele que criou a linguagem TEX na década de 70 e o famoso livro "The Art of Programming Computer". O exercício que citava o resultado começava mais ou menos assim:

"Observe que o número 9376 tem uma interessante propriedade reprodutiva tal que 9376 elevado ao quadrado é igual a 87909376..."

Bom, o resultado que percebemos não foi inédito, nem difícil, nem provavelmente muito importante, porém foi divertido e educativo encontrar mais esta simetria


Google