Exatas

Quem quer ser milionário?

Maneiras de se tornar rico de uma forma mais rápida: ganhar na mega-sena, ser um jogador de futebol, receber uma herança, estudar matemática… Estudar matemática!? Sim, ela pode ser um atalho para você se tornar milionário, mas para isso você terá de resolver um dos problemas que fazem parte dos denominados problemas do milênio. Um deles envolve uma matéria que aprendemos no ensino fundamental: os números primos.

Crédito da imagem: http://goo.gl/sVMvrg

Crédito da imagem: http://goo.gl/sVMvrg

Por volta de 300 a.c., Euclides formulou os primeiros teoremas sobre os números primos: 1. Há infinitos números primos e 2. Todo número maior do que um pode ser decomposto em um produto de números primos. Desde então o tema se tornou objeto de fascínio dos matemáticos, que procuram encontrar um padrão de distribuição desses números: 1, 3, 5, 7, 11, 13, 17, 19, 23… que, em uma observação rápida, já se mostra não ser trivial. Famosos matemáticos como Eratóstenes, Fermet, Euler publicaram estudos importantes sobre a distribuição de números primos, mas sem uma conclusão definitiva sobre o assunto. Riemann, orientado em seu doutorado por Gauss, formulou a hipótese de Riemann que é um dos sete seis (um deles já foi resolvido, mas o ator recusou o prêmio) problemas do milênio para cuja a solução (a prova da hipótese ou sua refutação) o Instituto Clay de Matemática oferece um prêmio de um milhão de dólares.

Ok! Mas qual a utilidade de se encontrar o padrão nessa distribuição? O que ela pode mudar em minha vida além de me tornar milionário? Ao provar a hipótese de Riemann a segurança da maior parte das empresas, órgãos governamentais e das pessoas estaria comprometida. O motivo? O RSA, que é o método de criptografia mais utilizado no mundo, utiliza chaves de criptografia que são geradas pelo produto de dois números primos gigantescos.

A utilização de números primos para a geração das chaves foi proposital. A fatoração para acha-los é um problema P vs NP, outro na lista dos problemas do milênio.  O problema P vs NP consiste em determinar se uma solução que pode ser verificada rapidamente (NP) possa também ser resolvida rapidamente (P), ou seja, se P = NP ou P ≠ NP. Exemplo prático disto no problema da fatoração: quais são os dois números primos que geram o número 13.717.421? Você consegue resolver isso de forma rápida sem consultar o Google? Provavelmente não (ao menos que você seja o personagem do filme O Cubo) . Porém, sabendo que o números 3.607 e 3.803 são os números primos que geraram este número basta realizar a multiplicação para verificar isso de forma rápida. Computacionalmente, também não temos um algoritmo que resolva o problema de forma rápida, ou seja, em tempo polinomial (a não ser em um computador quântico teórico), ou seja, atualmente o problema da fatoração, base da criptografia RSA, é um problema P ≠ NP.

Voltamos agora para falar novamente da hipótese de Riemann. Caso a hipótese seja comprovada, teremos um algoritmo de distribuição dos números primos que, ao ser usado, possibilitará a redução da complexidade do problema fatorial para polinomial (P = NP) e, consequentemente, não estaremos mais seguros mas, pelo menos, alguém estará milionário.

Fontes:
http://pt.wikipedia.org/wiki/Problemas_do_Pr%C3%A9mio_Millennium
http://www.repositorio.ufpe.br/handle/123456789/7361
http://pt.wikipedia.org/wiki/Teorema_fundamental_da_aritm%C3%A9tica
http://pt.wikipedia.org/wiki/A_quest%C3%A3o_P_versus_NP
http://blog.mhavila.com.br/2010/08/16/p-versus-np-continua-sem-solucao-comprovada/
http://csis.bits-pilani.ac.in/faculty/murali/netsec-09/seminar/refs/atharvasrep.pdf
http://paginapessoal.utfpr.edu.br/rwprobst/formacao-academica/curriculo/primos.pdf
http://pt.wikipedia.org/wiki/RSA

Anúncios

O Lendário Problema de Monty Hall

Suponha que você esteja em um programa de televisão, daqueles que distribuem prêmios através de jogos e brincadeiras. Na sua frente encontram-se três portas. Atrás de uma delas está o prêmio máximo do programa, um carro. Nas portas restantes, há uma cabra atrás de cada uma delas. O apresentador do programa pede que você escolha uma das três portas. Você, então, escolhe uma delas. Entretanto, ela não é aberta. O apresentador abre uma das outras portas que você não escolheu e mostra que há uma cabra atrás dela. Ele vira-se e diz que você tem uma última chance. Você pode permanecer com a sua escolha ou mudar para a porta que ainda não foi aberta. Diante dessa situação, o que você faria? Mudaria de porta ou permaneceria na mesma?

Em setembro de 1990, essa questão foi enviada por Craig F. Whitaker à Marilyn vos Savant. Marilyn trabalhava para a revista Parade e assinava uma coluna chamada ‘Pergunte a Marilyn’ (Ask Marilyn). Nessa coluna, Marilyn respondia questões matemáticas enviadas pelos leitores. A revista se orgulhava em dizer que ela tinha o QI mais alto do mundo, registrado pelo Guiness Book (livro que registra os maiores recordes mundiais).

Marilyn analisou a questão e respondeu que você SEMPRE deveria mudar. Dessa forma você aumentaria as suas chances de ganhar.

Sua resposta surpreendeu a todos. Se você pensar que, ao ser oferecida a oportunidade de mudar, sobram duas portas, então suas chances permanecem iguais, ou seja, 50% para cada lado (ganhar ou perder).

Uma avalanche de pessoas escreveram para a edição da revista alertando que Marylin estava errada (92% das cartas enviadas, para ser mais exato). O sistema educacional americano enfrentava a sua maior crise, e a relutância de Marylin em afirmar que a resposta estava correta, enfureceu a comunidade acadêmica e científica dos EUA. Vejam algumas coisas do que diziam:

“Eu estou muito preocupado com a falta de habilidade para a matemática do público em geral.
Por favor, ajude, confessando seu erro”
Robert Sachs, Ph.D., Universidade George Mason

“Há muita ignorância em matemática neste país e nós não precisamos que o QI
mais alto do mundo propague-a ainda mais. Que vergonha!”
Scott Smith, Ph.D., Universidade da Flórida

“Estou chocado que, mesmo depois de ser corrigida por, no mínimo, três matemáticos,
você ainda não admita o seu erro”
Kent Ford, Universidade Dickinson State

“Estou certo de que você receberá muitas cartas dos colégios e de estudantes
universitários. Talvez você deva guardar alguns endereços para
ajudarem-na em suas colunas futuras”
W. Robert Smith, Ph.D., Universidade Georgia State

“Você está completamente errada… Quantos matemáticos irados são necessários
para fazer você mudar de opinião?”
E. Ray, Ph.D., Universidade de Georgetown

“Se todos aqueles Ph.D.s estiverem errados, o país está com um problema muito sério”
Everett Harman, Ph.D., Instituto de Pesquisas do Exército dos EUA

Entretanto, ao explicar como solucionou o problema, Marilyn provou a todos que estava correta. Ela percebeu um detalhe que ninguém mais havia percebido. O apresentador, que sabe o que tem atrás de cada porta e, para manter a emoção do programa, nunca abrirá a porta que possui o carro atrás. Isso muda radicalmente a probabilidade de você ganhar o prêmio, caso opte por mudar a sua escolha. Observe atentamente a combinação de situações no diagrama abaixo:


A segunda linha mostra que, caso não mude a sua escolha, terá uma, em três, possibilidades de ganhar (1/3). Agora, caso resolva mudar, suas chances de ganho são de duas, em três, possibilidades (2/3). Ou seja, sempre mudando a sua escolha inicial, a sua probabilidade de ganhar o carro é muito maior.

Dessa história, podemos tirar duas grandes lições:

Primeira: Ter altos graus acadêmicos, evidentemente, aumenta a sua probabilidade de resolver problemas. Mas, não garante que você vai consegui resolver todos. É preciso ter mente aberta e humildade para que a arrogância não provoque cegueiras intelectuais.

Segunda: A unanimidade é burra! Muitas vezes nossa intuição pode cometer erros. É preciso analisar um problema de vários ângulos, e com diferentes visões. Afinal, o Sol passa todos os dias por sobre as nossas cabeças. E no entanto, não podemos concluir que ele gira em torno da Terra.

Um grande abraço e até a próxima!

A Matemática dos Padrões Invisíveis

Nas últimas décadas, o enorme avanço da tecnologia permitiu estudar muitos fenômenos naturais numa velocidade e precisão jamais experimentados antes. Com mais informações à mão, e novas matemáticas sendo desenvolvidas, começamos a constatar que havia muito mais ordem no caos do que conseguíamos perceber. Padrões invisíveis aos olhos, e seus inter-relacionamentos, passaram a brotar de todas as áreas do conhecimento humano.

Começamos a perceber alguns fatos curiosos, em teorias já consolidadas e dominadas, que ainda não conseguimos explicar satisfatoriamente. Por exemplo, suponha que você lance ao ar, uma moeda não-viciada, 100 vezes. Quais as chances de sair “cara” e “coroa” ao final desses lançamentos? Sabemos, pelas Leis da Probabilidade que, a “longo prazo”, aproximadamente 50% de todos os lançamentos serão “cara”. O mesmo vale para “coroa”. Certo!?

O que começou a intrigar os matemáticos foi o fato dos eventos não terem ligações entre si. Onde, e com o quê, está a memória para que o conjunto de lançamentos seja a metade para cada lado!? Os processos aleatórios envolvidos – ou, mais precisamente, os modelos matemáticos desses processos -, não possuem “memória”. O que estou querendo dizer é que, alguém ou alguma coisa “invisível”, teria que estar contando o número de ocorrências de cada amostra para concluir “Opa, está dando mais ‘cara’, agora tenho que fazer sair mais ‘coroa’ para que, no final, a quantidade seja 50% para cada”.

Outro exemplo de padrão escondido, que relaciona cidades com estudos de biologia, foi apresentado, em 1949, pelo linguista George Zipf, da universidade de Harvard. Zipf percebeu que, se tabulássemos as maiores cidades de um determinado país, classificando-as de acordo com suas populações, a maior cidade é sempre cerca de duas vezes maior que a segunda maior, e três vezes maior do que a terceira, e assim, sucessivamente. Em outras palavras, a população de uma cidade é inversamente proporcional à sua posição na escala de tamanhos.

A lei de Zipf, como ficou conhecida, tem sido verificada e comprovada durante os últimos 60 anos. Se pensarmos na quantidade de complexas variáveis como: condições sociais diferentes de cada país, políticas governamentais e de controle da natalidade, e os diferentes padrões de migração da década de 50 para cá, a generalidade e a exatidão da lei de Zipf são simplesmente espantosas.

Por volta de 2005, pesquisadores começaram a descobrir novas leis matemáticas sobre as cidades que são tão impressionantes quanto a lei de Zipf. Esses novos estudos estão nos ajudando a dimensionar a quantidade de infra-estrutura, necessária para uma cidade permanecer funcionando, à medida que sua população tende a crescer.

Se uma cidade é 5 vezes mais populosa do que outra, ela precisa de 5 vezes mais postos de gasolina? Não. Cidades maiores têm mais postos de gasolina (é claro), mas não na proporção de seu tamanho. O número de postos cresce apenas na proporção da potência 0,77 da população. Isto significa que, quanto maior uma cidade, menos postos de gasolina ela precisa ter por pessoa. Em outras palavras, as cidades maiores desfrutam de economias de escala. Contra-intuitivamente, nesse sentido, quanto maior e mais populosa for uma cidade, mais “verde” ela tenderá a ser.

Por que os três eventos, descritos acima, acontecem!? Ninguém sabe! E isso é só o começo.

O poder de interação, oferecido pelas redes sociais, possibilita o aumento da troca rápida de informações entre as pessoas. Isso instiga a criatividade e o senso de observação. Com mais pessoas interagindo (conversando) aumenta a probabilidade de alguém perceber algo que ninguém jamais tenha visto. Por outro lado, a mecânica lúdica, dos problemas descritos, pareceria totalmente acidental e aleatório, se não tivéssemos visto através das lentes da matemática. Sob essa ótica, e com o perdão da palavra à Adam Smith, a matemática é a linguagem que nos faz ver, e revelar, todas as verdades do mundo.