Uma proposta para o ensino de Combinatória

Combinatória é um assunto difícil, acho que todos concordamos com isso. Num curso típico sobre o assunto, logo na primeira ou segunda aula, conceitos sofisticados como combinação, arranjo, permutação são esparramados no quadro negro. Em breve virá a combinação com repetição e probabilidades e a coisa toda piora.

O aluno típico, frente a esta coleção de nomes e fórmulas procura desesperadamente respostas para suas angústias e invariavelmente ouvimos: "... mas neste exercícios, usamos combinação ou arranjo?"

Ensinar combinatória é igualmente frustrante, uma vez que não há uma sistemática a seguir e muitas vezes os professores são obrigados a tentar expressar sua própria intuição em palavras. Além disso a dificuldade de ensinar assunto tão simples agrava a sensação de frustração.

Princípio da Equiparação

Inspirado na forma como nossos antepassados realizavam contagem sem a utilização de números, vou propor uma nova abordagem para resolvermos exercícios de combinatória. Não é claro que ajudará todos os professores ou alunos mas é uma forma diferente que pode, acredito, ser bastante útil.

O grande segredo de nossos antepassados para contar, por exemplo, ovelhas de um rebanho é o chamado princípio da equiparação. Para cada ovelha do rebanho fazemos um talho num pedaço de pau. Assim, a quantidade de talhos na madeira é equivalente a quantidade de ovelhas. Se, no dia seguinte, houverem mais talhos do que ovelha é provável que algumas tenham sido roubadas ou mortas.

Se ao invés de talhos na madeira, utilizássemos pedras em um saco, não faria diferença nenhuma e o princípio da equiparação estaria sendo utilizado da mesma maneira. De fato muitas outras maneiras são possíveis e, se pensarmos um pouco, a escala numérica é apenas um substituto abstrato para o conjunto de talhos ou pedras em um saco.

Desta forma, contar uma coleção de elementos equivale a encontrar um conjunto de mesmo tamanho. Se este tamanho já é conhecido, não é necessário contar os elementos da coleção para conhecermos a resposta desejada. Por exemplo, apresento para vocês um auditório e informo que há 150 poltronas, na sequência pergunto: quantas pessoas sentadas poderemos acomodar? A resposta é óbvia; 150 pessoas.

Um Problema

O princípio da equiparação é uma ferramenta poderosa de contagem e procurarei ilustrar esta idéia através de um exercício bastante conhecido:

Suponha uma grade com 5 de largura e 3 de altura. Você está localizado no canto inferior esquerdo e deseja alcançar o canto superior direito. Só é possível a locomoção para a direita ou para cima. Quantos caminhos existem?

Certifique-se de que entendeu o problema. Desenhe a grade e trace alguns caminhos possíveis. Afinal, quantos existem? Se quiser pensar um pouco no problema interrompa a leitura neste ponto e volte mais tarde.

Adiantando já para a resolução, é possível perceber que cada caminho envolve 5 passos para a direita e 3 passos para cima. Se representarmos um passo para a direita pela letra D e um passo para cima pela letra C, todos os caminhos procurados podem ser representados por uma palavra de 5 letras D e 3 letras C's. Por exemplo, a palavra DCDDCCDD representa um dos caminhos enquanto CCCDDDDD representa outro.

Se pudermos concluir que a quantidade de palavras com 5 D's e 3 C's é exatamente igual a quantidade de caminhos que pretendemos contar, podemos contar as palavras ao invés dos caminhos e resolver o problema. Esta é a essência do princípio da equiparação.

Anagramas

Um anagrama é uma palavra formada a partir da reorganização das letras de outra palavra. Assim ROMA é um anagrama de AMOR. Palavra, no contexto que estou usando, não precisa ter nenhum significado, assim, a palavra MRAO também é um anagrama de AMOR.

A quantidade de anagramas de determinada palavra é assunto bastante estudado no ensino médio e não tratarei do assunto aqui. Digamos que no momento, calcular esta quantidade é um processo simples e de fácil entendimento.

Um pouco mais complicado é calcular a quantidade de anagramas de palavras com caracteres repetidos com por exemplo a palavra PASSEIO ou a palavra AUTOMATICO, mas novamente, há uma forma simples e sistemática de realizar esta contagem.

Se temos uma ferramenta para contar a quantidade de anagramas, por que não usá-la para resolver o problema proposto anteriormente, afinal a resposta do problema é a quantidade de anagramas que a palavra CCCDDDDD possui. Todos concordam?

Enfim, tínhamos um problema bem definido, conseguimos mapeá-lo para outro contexto, no caso o contexto dos anagramas que possuímos procedimentos fáceis de cálculo. Assim, usando o princípio da equiparação, contamos a quantidade de anagramas possíveis e automaticamente resolvemos o problema.

Um outro problema

Pensar em anagramas é uma boa maneira de resolver problemas de contagem em geral. Não estou querendo dizer que podemos sempre mapear um problema para um conjunto de anagramas, mas sim que sempre que pudermos a solução é imediata.

Um outro exemplo cuja solução por anagramas é simples é o seguinte:

Em um grupo de 9 pessoas conhecidas gostaríamos de eleger 2 presidentes, 3 diretores e 4 gerentes. De quantas maneiras podemos realizar a divisão?

Mais uma vez é possível modelar este problema usando a idéia de anagramas. Numere as pessoas de 1 a 10 e escreva na sequencia. Imediatamente abaixo destes números enfilere 9 letras, 2 P's para presidentes, 3 D's para diretores e 4 G's para gerentes.

123456789
PPDDDGGGG

Suponha que esta representação indica que as pessoas 1 e 2 são presidentes, as pessoas 3, 4, 5 são diretores enquanto as pessoas restantes são gerentes. É claro, muitas outras formações são possíveis, cada uma delas representada por um diferente anagrama da palavra PPDDDGGGG.

123456789
PPDDDGGGG
PDPGGGDGP
DGGGDPPDG
etc...

Assim o número procurado é exatamente igual ao número de anagramas da palavra PPDDDGGGG.

Generalização

Anagramas são ferramentas poderosas e na verdade generalizam os conceitos conhecidos de combinação, arranjo e permutação. Com isso quero dizer que toda combinação pode ser representada por um anagrama assim como todo arranjo e toda a permutação.

Por exemplo toda a combinação C(n,p) pode ser representada como a quantidade de anagramas de p X's e n-p Y's. Por exemplo C(7,3) é igual a quantidade de anagramas da palavra XXXYYYY.

Um arranjo A(n,p) pode ser representado pela busca de todos os anagramas de uma palavra com n-p letras distintas e n-p letras iguais. Assim A(7,3) é equivalente a quantidade de anagramas da palavra ABCXXXX.

Uma permutação de n elementos P(n) é sempre igual a quantidade de anagramas de uma palavra com n letras distintas. Exemplificando P(4) é equivalente a quantidade de anagramas da palavra AMOR.

Conclusão

O princípio da equiparação é muito útil para resolver um sem número de problemas. Suponho que aulas de combinatória focadas neste tipo de raciocínio caminharão no sentido do fortalecimento de conceitos ao invés de memorização de fórmulas. Os anagramas são apenas um exemplo de conjunto que podemos utilizar na aplicação do princípio da equiparação. Eles naturalmente não esgotam o assunto mas é uma nova ferramenta na tentativa de despertar a intuição de alunos e professores.

O Segredo

Por mais incrível que nos possa parecer o princípio da Contagem é mais antigo do que o conceito de número, isto é, nossos antepassados conseguiam contar antes mesmo da humanidade conhecer ou inventar os números.

Suponha que você leitor é submetido a uma máquina do tempo que o transporta para uma época onde os números não eram conhecidos. De alguma maneira esse conhecimento também lhe é retirado porém sua inteligência e capacidade física são preservadas. Uma peculiar comunidade o recebe e, surpreendentemente, lhe oferece uma importante posição. Enfim, você é designado Pastor de Ovelhas.

Honrado com sua sua nova atribuição, logo toma conhecimento da expectativa da comunidade para com sua atuação em tão nobre ofício: certificar que o rebanho está sendo bem tratado; garantir que não haja predadores nem ladrões por perto; verificar se a cerca está livre de furos ou descontinuidades de modo que nenhum animal possa fugir; alertar a autoridade local de uma iminente escassez ou superpopulação.

Ansioso por mostrar resultados, você começa imediatamente a trabalhar e logo se defronta com alguns problemas que requerem rápida solução. Há muitas ovelhas para pastorear e é praticamente impossível diferenciar uma ovelha das outras, assim não é simples perceber se algumas foram roubadas ou devoradas por algum predador.

Confiante, você acredita que sua mente avançada, proveniente do futuro, logo irá encontrar uma solução para aquela milenar e trivial tarefa. Estranhamente, nada lhe vem a cabeça e os dias vão passando. Quando questionado sobre a saúde do rebanho, você, num sentimento entre vergonha e agonia, mente, dizendo que tudo vai bem, porém na realidade você não sabe mais hoje do que no dia em que chegou.

Um dia você toma conhecimento de que o antigo pastor ainda vive e que, apesar de velho, está lúcido e gosta de companhia. Aliviado você o procura em busca de aconselhamento e é neste dia que você descobre o grande segredo.

Hoje sabemos que a ferramenta de contar as ovelhas é essencial para o ofício de Pastor, porém nesta época números não eram conhecidos. Qual é afinal o grande segredo que o ancião lhe contou?

Simplício

Galileu Galilei foi obrigado a responder diante do tribunal da Santa Inquisição porque escreveu um livro que contrariava os dogmas da Igreja. "Diálogo sobre os Dois Máximos Sistemas de Mundo" foi escrito na forma de um diálogo entre três personagens: Salviati, o defensor do ponto de vista de Galileu que, seguindo os passos de Copérnico, colocava o Sol ao centro do Universo; Simplício que defendia a posição da igreja com a Terra ao centro do universo e Sagredo, uma espécie de mediador do diálogo.

O papa Urbano VIII obviamente se enfureceu com a escolha destes nomes, afinal a sua posição e a da igreja era defendida por alguém de nome Simplício. Tamanho erro estratégico colocou Galileu, religioso devoto e amigo do papa, em prisão domiciliar até o fim de seus dias.

Recebi de meu antigo chefe um relato de um episódio que ocorreu nos últimos dias. Trata-se de um evento cotidiano protagonizado por ele mesmo e um subordinado de alta patente da área de desenvolvimento de software. O acontecimento foi narrado de modo um tanto jocoso e de fato, para quem conhece os envolvidos, é muito engraçado. Reproduzirei aqui o relato, porém, para preservar a identidade dos protagonistas, optei por mudar seus nomes à moda de Galileu Galilei. Acompanhe abaixo, observando que minhas alterações e comentários estão em negrito.

Nós aqui na empresa temos 3 vagas no subsolo que estão sendo utilizadas por mim (Salviati), pelo Fulano (coadjuvante) e pelo Simplício. Como a garagem é pequena, o prédio utiliza serviços de manobristas que ficam na garagem até a hora em que nossos carros estejam posicionados para podermos sair sem a necessidade de manobrar outros carros. Quando estão nesta situação, o manobrista deixa todas as chaves na portaria que fica no andar térreo.

Sexta-feira, à noite, eu e o Simplício saímos da empresa e nos dirigimos à portaria (térreo) para pegar as nossas chaves. Reconheci e peguei a minha chave, pois utilizo um chaveiro com um cifrão para dar sorte, mas percebi Simplício confuso, com duas chaves idênticas de Mercedes (sim, pasmem, Simplício tem um Mercedes), fazendo aquela cara de interrogação. Ele pensou, pensou, tentou verificar se havia alguma marquinha na chave que pudesse fazê-lo concluir qual seria a sua, mas nada, nenhuma marquinha. Concluiu ele que o melhor seria levar as duas chaves ao subsolo, experimentá-las e trazer de volta a errada. Eu, não aguentando, interferi: Por que trocar 50% de chances de você não precisar retornar por 100% de certeza de que você precisará retornar para devolver a chave errada? Ele continuou com cara de interrogação. Como sempre, tive que explicar em detalhes: Por que você não escolhe uma das chaves e desce, se acertar, não precisa voltar, se errar, volte e pegue a outra chave que será a correta. Depois da segunda explicação e de alguma ajuda do porteiro Sagredo, fazendo um pequeno teatro, ele enfim entendeu e feliz falou: Por isso que você é o chefe!!! (sim, Simplício é capaz deste tipo de comentário apaspalhado)

Envergonhado por uma declaração desta na frente do porteiro Sagredo que me olhou com aquela cara de “você só contrata débeis mentais, para se sentir superior a eles”, desci com Simplício e “voilá”: ele acertou na escolha da chave e não precisou voltar à portaria. Triste pelo ocorrido, devo ter gerado alguma energia negativa que meu carro nem funcionou direito. Por outro lado, o Simpício viu a outra Mercedes que estava na garagem e lamentou não ter escolhido a chave errada.

Conheço Salviati e Simplício há muitos anos e me diverti muito lendo o relato acima enviado por Salviati. Simplício é Arquiteto de Software Sr, com mestrado, Mercedes e tudo o mais, só espero que não se ofenda muito por ter publicado esta história no Blog. É certo que omiti sua identidade mas aqueles que o conhecem saberão sobre quem estou falando. De qualquer forma, a mensagem que quero deixar é outra. Muitas pessoas reclamam da Matemática porque acham que ela não tem aplicação prática e que não serve para nada. Penso diferente, acho que nós não percebemos quando a Matemática se materializa em nossa frente.

Beleza da Matemática

Oi, Alexandre
Não o conheço mas, aproveitando seus comentários, creio que seria interessante que vc, um matemático, explorasse um pouco mais o que é essa "beleza" da simetria matemática e que nesse "encontro" tanto o fascinou!
Em outras palavras, o que há aí que chamamos de "belo"?
Fale-nos um pouco mais sobre isso...
Abs

Olá Fernando,

Sua pergunta é profunda e bastante difícil de responder. Toda a vez que tento definir a beleza da matemática para outra pessoa percebo que o interlocutor não sentiu de fato o que eu gostaria de passar.

Porém, tenho certeza de que muitas pessoas, em especial muitos matemáticos, compartilham da minha opinião de que a matemática é antes de tudo bela. No processo de descoberta é comum caracterizarmos o desenvolvimento realizado como "belo" ou "elegante". Frases como "Que belo teorema !", "Aquela demonstração é muito sutil e elegante." são recorrentes no meio matemático.

Na verdade não sei definir o conceito de beleza, nem no sentido geral, nem no sentido matemático, se é que são diferentes. Mas posso dizer que em matemática, a beleza está próxima de simplicidade, clareza, originalidade e surpresa.

Em geral, uma demonstração curta e simples é mais bela do que uma demonstração longa. Um resultado claro, de fácil entendimento, é mais belo do que um resultado complexo que demanda muito esforço para sua compreensão. Um desenvolvimento original, ousado, criativo, fora do comum, será sem dúvida reconhecido como belo.

Se além de tudo isso, a demonstração causar surpresa, é bastante provável que o leitor a considere assombrosamente bela. "Surpreendente!" ele dirá e nunca mais vai esquecer o teorema. Há vários exemplos bastante conhecidos de teoremas que são unânimamente considerados belos, como a prova atribuída a Euclides da Infinidade dos Números Primos, ou a demonstração de que a diagonal do quadrado é um número irracional.

Quando uma pessoa curiosa, mas não matemática lê ou escuta que há uma prova de que existem infinitos números primos ela provavelmente pensará: Como alguém pode provar que existem infinitos elementos de alguma coisa? Se esta mesma pessoa ler e entender a demonstração, perceberá que não há alternativa alguma a não ser que, de fato, existam um número infinito de números primos. Isso causará surpresa, prazer intelectual e o contato com uma sensação de VERDADE nunca experimentada anteriormente.

A verdade e a certeza que a matemática nos traz não pode ser subestimado na construção da nossa percepção da beleza. Nossa vida é repleta de incertezas, não sabemos se vamos ter emprego no mês que vem, se vamos ser bem sucedidos neste ou naquele projeto, se nossos filhos vão ser felizes, etc..., etc... etc... mas EXISTEM INFINITOS NÚMEROS PRIMOS. Parece bobo comparado com nossas necessidades reais mais o tipo de certeza que a matemática fornece, nos traz conforto, alento, e por que não, prazer. Trazendo prazer, queremos contemplar mais e mais esta verdade. Enfim, o que dizemos quando queremos contemplar algo mais tempo? Que este algo é belo.

É impossível esgotar o assunto e tenho a impressão de que qualquer linha argumentativa é pobre frente a contemplação de uma demonstração real que pretendo mostrar para finalizar este texto.

Para sair do lugar comum apresentarei uma demonstração não muito conhecida que acho muito bela atribuída ao matemático medieval Nicolau Oresme relacionado com a soma de uma série infinita.

Sabemos que a soma 1 + 1/2 + 1/4 + 1/8 + ... é igual a 2. Este resultado por si só é bastante surpreendente afinal estamos somando infinitos termos e obtendo um número finito, isto é 2.

Da mesma forma 1 + 1/3 + 1/9 + 1/27 + ... é igual a 3/2. De novo, uma soma infinita resultando num valor finito. E isso vale para qualquer série da forma 1 + 1/k + 1/kk + 1/kkk + ...., se k for maior do que 1.

Agora, e a série 1 + 1/2 + 1/3 + 1/4 + 1/5 + ...? Ela é igual a um valor finito ou ela é igual a infinito como é a série 1 + 1 + 1 + 1 + ...?

Oresme mostrou que a série 1 + 1/2 + 1/3 + 1/4 + 1/5 + ..., também chamada de série harmônica, é igual a infinito, formalmente Oresme provou que a série harmônica é divergente. Observe a simplicidade e elegância da demonstração.

Note que:

1/3 + 1/4 > 1/4 + 1/4 portanto 1/3 + 1/4 > 1/2

1/5 + 1/6 + 1/7 + 1/8 > 1/8 + 1/8 + 1/8 + 1/8 portanto 1/5 + 1/6 + 1/7 + 1/8 > 1/2

1/9 + 1/10 + ... + 1/16 > 1/16 + 1/16 + ... + 1/16 (8 vezes 1/16) portanto 1/9 + 1/10 + ... + 1/16 > 1/2

Podemos portanto reescrever 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ... como 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ...

Enfim,

1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ... > 1 + 1/2 + (1/2) + (1/2) + ...

Ora sabemos 1 + 1/2 + (1/2) + (1/2) + ... é igual a infinito. Então, obviamente 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ... também é igual a infinito.

Bom não sei se você irá achar bela esta demonstração, afinal beleza é pessoal, mas tenho certeza de que há alguma demonstração, algum resultado que você irá considerar belo ou elegante ou interessante.

Um abraço

Alexandre

Fios de cabelo em São Paulo

Existe uma anedota bastante conhecida sobre os matemáticos. O sujeito está num balão que vaga a esmo sobre um grande deserto. Perdido, ele avista um andarilho na linha do horizonte. Por sorte os ventos o levam até uma distância próxima do andarilho. Lá de cima o sujeito grita:

— Eeeeeeeeiiiii, aí embaixo! Onde é que estou?
O andarilho observa, analisa e responde:
— Você está num balão.
Diante desta resposta o sujeito, atônito, retruca.
— Você é um matemático, não é?
— Sim, como você sabe?
— Bom, sua resposta é absolutamente correta e não serve absolutamente para nada.

Essa piada é o que podemos chamar de "piada genérica" e é muitas vezes customizada para outras profissões, é possível que vocês já a tenham ouvido interpretada por outros atores, como os Consultores ou mesmo os Estagiários, mas nenhum possui um perfil tão adequado quanto os Matemáticos aos propósitos da piada.

Sim, a matemática está preocupada com a verdade, tão preocupada que preferimos muitas vezes falar o óbvio a correr o risco de cometer uma imprecisão. É surpreendente que falando o óbvio o tempo todo alcançamos verdades não tão claras assim, fato que pretendo ilustrar para vocês.

Na cidade de São Paulo existem duas pessoas com a mesma quantidade de fios de cabelo?

Procurem responder a questão acima. Imagino que uma série de respostas serão possíveis. Enumero alguma delas:

1) Acho que não.
2) Acho que sim.
3) Não podemos afirmar com certeza.
4) Não, é claro que não.
5) Sim, com certeza sim.
6) Sim, dois carecas tem zero fios de cabelo.

Para acabar com a alegria de quem respondeu a resposta (6), consideramos que não há carecas, ou se preferirem, que trocamos cada careca por uma pessoa com cabelo de outras cidades.

Neste ponto, volto a insistir na pergunta, existem ou não existem duas pessoas com a mesma quantidade de fios de cabelo. O que diz a intuição de vocês? O meu palpite é que a grande maioria responderá algo próximo das repostas (1), (2) ou (3). Estou certo?

Bom, agora vou provar, isso mesmo, provar, que com certeza existem duas pessoas na cidade de São Paulo com a mesma quantidade de fios de cabelo. Para tanto, lançarei mão de dois axiomas, duas premissas que uma vez aceitas, se tornarão verdades irrefutáveis no desenvolvimento do raciocínio.

• (Axioma I) Nenhuma pessoa possui mais de 1 metro quadrado de couro cabeludo.

• (Axioma II) Nenhuma pessoa possui mais de 1000 fios de cabelo por centímetro quadrado de couro cabeludo.

Para mim é razoável que não existam pessoas na cidade de São Paulo que violem qualquer um dos axiomas propostos. Agora, se vocês discordam é porque conhecem tal aberração e nesse caso sugiro interromper o artigo e levar seu amigo para qualquer programa de televisão que aprecie este tipo de atração.

Bom, se chegou aqui é porque aceitou os axiomas. Nesse caso, é simples concluir que nenhum ser humano pode ter mais do que 10.000.000 fios de cabelo. Note que se qualquer pessoa tiver mais do que 10.000.000 fios terá quebrado um ou os dois axiomas.

Neste ponto, devemos escolher alguém para realizar o trabalho da contagem. Para dificultar, vou escolher um "recenseador capilar" corrupto, disposto em troca de uma boa soma em dinheiro, a provar o contrário, isto é, que não existe empate de número de fios de cabelo em São Paulo. Como instrumento de trabalho o recenseador receberá uma lista numerada de 1 a 10.000.000 e seu trabalho será marcar ao lado de cada número quantas pessoas foram encontradas.

O recenseador inicia, então, seu trabalho. Escolhe a primeira pessoa, conta 2347 fios, a segunda 1230, a terceira 4007 e assim vai, contando e anotando na sua lista.

Em determinado momento, ele se depara com o número 4007 novamente, aquele mesmo encontrado para a terceira pessoa avaliada. Se ele marcar novamente 4007, haverá duas pessoas com aquele mesmo número. Disposto a adulterar a informação, ele olha para os lados e disfarçadamente considera 4008, número ainda não utilizado.

Depois de meses de trabalho, o recenseador já coletou 10.000.000 números, isto é, ainda faltam 2 ou 3 milhões para completar o trabalho, afinal, todos sabemos que São Paulo tem bem mais do que 10 milhões de habitantes.

Ao pegar a caneta para registrar o próximo número, nosso recenseador percebe ( tardiamente pensará o leitor mais perspicaz) que todos os números já estão ocupados e não resta alternativa para ele, mesmo adulterando os resultados, a não ser repetir algum número. Enfim, aceito os axiomas, com certeza existem em São Paulo duas pessoas com a mesma quantidade de fios de cabelo.

O raciocínio acima é baseado no Princípio da Casa dos Pombos, princípio que afirma que se n pombos devem ser postos em m casas, sendo n > m, então pelo menos uma casa irá conter mais de um pombo. Apesar de se tratar de um fato extremamente elementar e óbvio, o princípio da casa de pombos é útil para resolver problemas que não são imediatos. Naturalmente, quando aplicamos o princípio devemos identificar quem são os "pombos" e quem são as "casas" de nosso problema.

Espero que vocês tenham acompanhado o raciocínio e percebido que, mesmo se escolhermos um recenseador viciado, a conclusão será a mesma. O desenvolvimento acima é uma demonstração matemática como qualquer outra apesar de utilizar um formato pouco usual. A partir de um conjunto de axiomas, realizamos deduções até chegamos ao resultado esperado.

Não sei se esse resultado o impressiona mas quando percebi isso pela primeira vez fiquei bastante intrigado com o fato de que, mesmo sem contar cada caso, posso ter certeza desta informação por um raciocínio indireto, mas totalmente válido e irrefutável.

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...

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:

3n²-2n³ (mod 10^2d(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 3n²-2n³ por 10^2d(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 R₅(d) + R₆(d), onde R₅(d) representa o maior número auto-reprodutivo de cauda 5 que possui d ou menos dígitos, analogamente R₆(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 é:

R₅(d) + R₆(d) = 10^d + 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