Cultura e História >> Na Mídia >> Solução para problema do Chapéu

Solução para problema do Chapéu Texto de New York Times de 16.04.2001. Vicente Eudes para FLP

BERKELEY, Califórnia - É necessário um problema especialmente complicado para confundir a mente de alguém que esteja acostumado a fazer "ginástica mental". Realmente, o desafio que está dando trabalho a vários grupos de matemáticos, não diz respeito a um probleminha comum. Conhecido como "o problema do chapéu", na sua versão mais popular, esse quebra-cabeças aparentemente simples está consumindo cérebros nas universidades e laboratórios de pesquisa do país, e se tornou um acalorado tópico de discussão na Internet. De acordo com os matemáticos, a razão pela qual esse problema cativa tanta gente é que não se trata de apenas uma charada recreativa para ser resolvida e colocada de lado. Pelo contrário, ele tem conexões profundas e inesperadas com a teoria da codificação ou encriptação, uma área ativa da pesquisa matemática, com amplas implicações para as telecomunicações e a ciência da computação. Ao tentar encontrar uma solução completa para o problema, os matemáticos estão testando novos teoremas em teoria da codificação, que podem ser aplicados em áreas que vão além dos problemas matemáticos. "Esse problema é único, já que conecta questões matemáticas não resolvidas", diz Joe Buhler, diretor do Instituto de Pesquisas de Ciências Matemáticas, aqui em Berkeley, e um pesquisador entusiasmado do problema do chapéu. O problema do chapéu consiste no seguinte: Três jogadores entram em uma sala e um chapéu vermelho ou azul é colocado na cabeça de cada um. A cor de cada chapéu é determinada por um jogo de cara ou coroa. O resultado de cada lançamento da moeda não tem efeito algum sobre as outras jogadas. Cada jogador pode ver o chapéu dos outros, mas não o seu próprio. Não é permitida comunicação de espécie alguma entre os jogadores, com exceção de um encontro para discussão de estratégia antes do início do jogo. Tão logo tenham a oportunidade de ver os chapéus dos companheiros, os jogadores devem adivinhar simultaneamente a cor dos seus próprios chapéus, ou ficar calados. O grupo dividirá um prêmio hipotético de US$ 3 milhões (R$ 6,46 milhões) se pelo menos um dos jogadores adivinhar as cores dos chapéus e se nenhum deles adivinhar incorretamente. Pode participar do jogo qualquer número de jogadores. O problema geral é encontrar uma estratégia para que o grupo maximize as suas chances de ganhar o prêmio. Uma estratégia óbvia a ser utilizada pelos jogadores seria, por exemplo, que um dos jogadores sempre "adivinhasse" vermelho, enquanto que os outros permanecessem em silêncio quando chegasse a sua vez. Isso daria ao grupo uma chance de 50% de ganhar o prêmio. Mas será que o grupo poderia fazer melhor do que isso? A princípio, a maioria dos matemáticos acha que não. Considerando que a cor do chapéu de cada pessoa independe da cores usadas pelos outros, e que nenhuma comunicação é permitida entre os jogadores, parece impossível que os participantes descubram qualquer coisa apenas olhando para os outros. Aparentemente, tudo o que os jogadores podem fazer é adivinhar. "Quando explico o problema a uma pessoa, a única coisa que ela pensa é que não há condições para resolve-lo", diz Peter Winkler, diretor de pesquisas com matemática fundamental nos Laboratórios Bell de Tecnologias de Luz, em Murray Hill, Nova Jersey. "Por outro lado, ao se tentar provar que a solução do problema é impossível, não se chega a resultado algum". Os matemáticos atribuem a autoria do problema a Todd Ebert, um instrutor de ciência de computação da Universidade da Califórnia em Irvine, que introduziu a charada na sua tese de doutorado pela Universidade da Califórnia em Santa Barbara, em 1998. Ebert afirma que só recentemente percebeu as implicações do problema, quando ofereceu créditos extras aos seus estudantes para que resolvessem uma versão de sete jogadores, chamada de "o problema dos sete prisioneiros". Ebert conta que, depois disso, o problema passou a ser divulgado nos grupos e salas de discussão da Internet. "Passei a receber e-mails de todo o país", diz Ebert. Enquanto isso, Winkler, um coletor e distribuidor conhecido de desafios inteligentes, ouviu falar sobre o problema do chapéu, através de um colega, e o difundiu amplamente. O problema passou pelo Centro de Pesquisas da Microsoft, em Redmond, Washington, pelos laboratórios da Hewlett-Packard, em Palo Alto, Califórnia, e por departamentos de matemática, estatística e ciência da computação de universidades de todo o país. O problema do chapéu foi parar até no Caribe. Durante um seminário em um instituto de pesquisas em Barbados, um grupo de cientistas teóricos de computação passou toda uma noite às claras, tomando rum, em um jogo de bebidas baseado no problema. O desafio se disseminou em Berkeley, depois que Winkler encontrou Elwyn Berlekamp, professor do departamento de matemática da Universidade de Berkeley, em uma conferência em Nova Orleans, em janeiro deste ano. "Eu falei a ele sobre o problema e passei a receber mensagens na secretária eletrônica do meu hotel, dizendo, 'É um grande problema, ainda não o resolvi'. Até que um dia havia a mensagem, 'Problema resolvido!', diz Winkler. "Eu achei que, com o seu conhecimento de teoria da codificação, Berlekamp tivesse descoberto uma solução, e ele não me desapontou". Berlekamp, um especialista em teoria da codificação, afirmou que havia descoberto uma solução para o caso mais simples em cerca de meia hora, mas que só havia percebido a conexão com a teoria da codificação quando tinha ido dormir. "Se olharmos para questões antigas que conhecemos por um ângulo diferente, algumas vezes não conseguimos vê-las", explica o cientista. O primeiro detalhe percebido por Berlekamp foi que , no caso dos três jogadores, é possível que o grupo ganhe em três quartos das tentativas. Em três quartos das jogadas, dois dos jogadores terão chapéus da mesma cor, e o chapéu do terceiro jogador vai ter a outra cor possível. O grupo pode ganhar sempre que isso ocorrer, utilizando a seguinte estratégia: tão logo se inicie o jogo, cada jogador examina a cor do chapéu dos outros dois. Se os dois chapéus forem de cores diferentes, ele se abstém de dar um palpite. Se forem da mesma cor, o jogador diz que o seu chapéu é de cor diferente. Dessa forma, todas as vezes que as cores dos chapéus estiverem distribuídas em uma razão de dois para um, um dos jogadores vai dar um palpite correto, enquanto os outros dois vão se abster de adivinhar, e o grupo ganhará o jogo. No entanto, quando os três chapéus tiverem a mesma cor, todos os jogadores darão um palpite errado, e o grupo perderá. "Se examinarmos o número total de adivinhações, perceberemos que metade é certa e metade é errada", afirma Winkler. "Só se progride no jogo se, quando os jogadores estiverem dando palpites errados, a maioria estiver errada". A estratégia fica bem mais complicada para um número maior de jogadores. Ainda assim, tudo se resume a assegurar que na maioria das vezes ninguém esteja errado e que, ocasionalmente, todos estejam errados simultaneamente. Conforme se descobriu, essa exigência só pode ser perfeitamente satisfeita quando o número de jogadores for menor do que uma potência de dois (três, sete, 15, e assim por diante). Por exemplo, em um jogo com 15 jogadores, há uma estratégia para a qual o grupo sai vencedor em 15 vezes a cada 16 jogadas. Essa estratégia pode ser descrita por meio de elegantes estruturas matemáticas conhecidas como códigos Hamming. Esses códigos, que têm esse nome em homenagem a Richard Hamming, o matemático que os descobriu, são ferramentas básicas estudadas por estudantes de engenharia do mundo todo. Os códigos Hamming definem a fronteira entre dois tipos de objetos matemáticos: os códigos de correção de erros e os códigos de ocultação. Os códigos de correção de erros, técnicas para a correção de erros em dados enviados através de canais ruidosos, são utilizados em uma série de dispositivos, desde aos telefones celulares até os discos compactos. Os códigos de ocultação podem ser utilizados para a compressão de dados, de forma que esses ocupem menos espaço na memória dos computadores. "Os códigos Hamming são estruturas perfeitas, semelhantes a cristais, no sentido de que não se pode mover um átomo sequer sem que se destrua completamente a estrutura", explica Amin Shokrollah, cientista chefe da Digital Fountain, que utiliza a teoria da codificação para acelerar as transmissões de dados via Internet. "Quando se examina atentamente a essência do problema do chapéu, descobre-se que aquilo de que se necessita são exatamente os códigos Hamming". Quando se joga com menos de nove participantes, a melhor solução pode ser determinada por meio da utilização de vários tipos de códigos. Para números maiores de jogadores, que não sejam menores em uma unidade do que uma potência de dois, uma estratégia elaborada com base na solução encontrada com os códigos Hamming funciona em quase 100% dos casos, conforme aumenta o número de participantes do jogo. Hendrik Lenstra, professor de matemática em Berkeley, e Gadiel Seroussi, diretor de pesquisa em teoria de informações nos laboratórios da Hewlett-Packard, desenvolveram um novo tipo de código de ocultação, para definir uma estratégia ainda melhor para um número maior de jogadores. Embora essa estratégia seja, até o momento, a melhor, não se sabe se ela é sempre a derradeira. A solução derradeira para o problema do chapéu, para qualquer número de jogadores, ainda é desconhecida. "Ainda estamos trabalhando para encontrar uma solução", diz Seroussi. "E, como conseqüência de estarmos trabalhando no problema, temos alguns resultados em teoria da codificação que são interessantes por si próprios". Por enquanto, segundo os pesquisadores, parece improvável que se encontre uma solução com imediatas aplicações práticas. Ainda assim, nunca se sabe o que o futuro reserva para o problema do chapéu. "A minha experiência diz que todo trabalho matemático cedo ou tarde termina demonstrando ter alguma utilidade", diz Seroussi. Tendo ou não uma utilidade prática, para alguns pesquisadores o problema do chapéu possui importantes implicações sociais. "Gosto de problemas que têm implicações filosóficas", diz Berlekamp., citando duas lições de vida que podem ser extraídas do problema: "A primeira é não há problemas em se cometer erros, contanto que se tome providências para que não se erre sozinho", diz ele. "A outra lição, que é mais importante, diz respeito à necessidade de um trabalho de equipe que vai contra a intuição da maioria dos matemáticos. Se a evidência sugerir que alguém na sua equipe sabe mais do que você, deve-se ficar calado. A maioria de nós acredita que a estratégia de cada jogador objetiva um acerto individual. Mas isso não é verdade. Trata-se de toda a equipe". Tradução: Danilo Fonseca