15/08/2018

Problemas matemáticos: o fácil pode ser muito difícil

Há um exemplo espetacular de como um problema matemático pode ser facílimo de formular e dificílimo de resolver.

Funciona assim: considere um inteiro positivo N qualquer. Se for par, divida por 2. Se for ímpar, multiplique por 3 e some 1. Substitua N pelo resultado obtido e siga repetindo esse procedimento. Por exemplo, se começar com N=7 obterá, sucessivamente, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 e, a partir daí, a sequência só repete os números 4, 2, 1, ciclicamente.

Se começar com outro valor de N, a sequência será diferente, claro, porém mais cedo ou mais tarde chegará ao número 1. O número de operações até isso acontecer, chamado tempo de paragem, depende de maneira complicada do número inicial N. Mas cedo ou tarde sempre acontece.

Pelo menos foi assim para todos os números testados até hoje. Com o advento dos computadores, tornou-se possível testar números cada vez maiores; hoje em dia sabemos que a propriedade de chegar ao número 1 vale, pelo menos, para todos os números N com menos de 21 dígitos.

Mas ninguém conseguiu ainda dar uma prova matemática rigorosa de que ela valha para todos os inteiros, apesar de todos os esforços feitos desde que o problema foi levantado, em 1928, pelo matemático alemão Lothar Collatz (1910–1990). Na verdade, houve pouquíssimos avanços.

O famoso matemático húngaro Paul Erdös (1993 –1996) disse uma vez que “talvez a matemática não esteja pronta para problemas como este”, querendo dizer que não existem ferramentas para atacá-lo. Ele também ofereceu US$ 500 pela solução, e esse prêmio continua valendo.

Um avanço interessante, que também ilustra a sutileza do problema, foi obtido por John Conway e melhorado por Stuart Kurtz e Janos Simon. Num contexto um pouco mais geral, eles provaram que o problema é computacionalmente indecidível: não existe nenhum programa de computador capaz de dizer para todo N se a sequência vai chegar ao 1 ou não.

Para ler o texto na íntegra acesse o site do jornal ou confira na versão impressa

A Folha permite que cada leitor tenha acesso a dez textos por mês mesmo sem ser assinante.