Esse é uma verdadeira areia movediça mental para os matemáticos. Eles aconselham uns aos outros a ficarem bem longe dessa famosa conjectura....
Esse é uma verdadeira areia movediça mental para os matemáticos. Eles aconselham uns aos outros a ficarem bem longe dessa famosa conjectura. Se você não a conhece, continue por sua conta e risco. Mas, apesar de todos esses alertas, Terence Tao, um proeminente matemático, estudou o problema. E fez o maior progresso em décadas.
Parece o enunciado de um truque de mentalismo: Escolha um número, qualquer número inteiro positivo. Se for par, reduza para metade. Se for ímpar, multiplique por 3 e adicione 1. Repita. Todos os números iniciais levam a 1?
A conjectura é justamente sobre o que acontece se você continuar repetindo o processo. Intuitivamente podemos achar que o número com o qual você começa acabe afetando o número com o qual você termina. Alguns números talvez cheguem a 1. Outros talvez continuem em uma sucessão infinita de cálculos. (No final do post há uma calculadora para você calcular a série a partir de um número inteiro positivo).
Lothar Collatz provavelmente apresentou sua conjectura na década de 1930. previu que não é esse o caso. Ele conjecturou que, se você começar com um número inteiro positivo e executar esse processo por tempo suficiente, todos os valores iniciais levarão a 1. E quando você chegar a 1, as regras da conjectura de Collatz farão você entrar em um ciclo repetitivo para sempre: 1, 4, 2, 1, 4, 2, 1...
Ao longo dos anos, foram muitos os que se deixaram seduzir por essa espécie de "caneta azul" matemática. Um chiclete mental aparentemente inocente e provavelmente inútil. Sua simplicidade fez inúmero matemáticos e entusiastas da matemática literalmente perderem tempo tentando resolver o problema "3x + 1". Como também é conhecido.
Foram testados quintilhões de exemplos (18 zeros) sem encontrar uma única exceção à previsão de Collatz. A Internet está repleta de provas amadoras infundadas que afirmam ter resolvido o problema de uma alguma forma.
Na década de 1970, matemáticos mostraram que quase todas as seqüências de Collatz - a lista de números que você obtém ao repetir o processo - chegam a um número menor do que onde você começou - evidências consideradas fracas de que quase todas as sequências de Collatz se inclinam para 1.
Finalmente, uma novidade
Terence Tao não é do tipo que fica investindo tempo em problemas fúteis. Em 2006, ele ganhou a Medalha Fields, a maior honra da matemática, e ele é amplamente considerado como um dos principais matemáticos de sua geração. Ele está acostumado a resolver problemas, não a perseguir delírios.
Todavia, Tao não resiste inteiramente aos cantos das sereias de seu campo de atuação. Todos os anos, ele se arrisca por um dia ou dois em algum dos famosos problemas ainda não resolvidos da matemática. Ao longo dos anos, ele fez algumas tentativas para resolver a conjectura de Collatz, sem sucesso.
Mas isso mudou em agosto deste ano quando um leitor anônimo deixou um comentário no blog de Tao sugerindo que ele resolvesse a conjectura de Collatz para "quase todos" números, em vez de tentar resolvê-la completamente.
E fo aí que ele notou que a conjectura de Collatz era semelhante, em alguma medida, aos tipos de equações - chamadas equações diferenciais parciais (PDE, na sigla em inglês) - que apareceram em alguns dos resultados mais significativos de sua trajetória.
As PDEs podem ser usadas para modelar muitos dos processos físicos mais fundamentais do universo, como a evolução de um fluido ou a ondulação da gravidade no espaço-tempo. Elas surgem em situações em que a posição futura de um sistema - como o estado de uma lagoa 5 segundos após de você atirar uma pedra nela - depende de contribuições de dois ou mais fatores, como a viscosidade e a velocidade da água.
Apesar de PDEs complicadas não parecerem ter muito a ver com uma pergunta simples sobre aritmética como a conjectura de Collatz, Tao percebeu que havia algo semelhante neles. Com um PDE, você conecta alguns valores, obtém outros valores e repete o processo - tudo para entender esse estado futuro do sistema. Para qualquer PDE, os matemáticos querem saber se alguns valores iniciais acabam levando a valores infinitos como saída ou se uma equação sempre produz valores finitos, independentemente dos valores com os quais você começa.
Para ele, esse objetivo tinha o mesmo sabor de investigar se você sempre obtém o mesmo número (1) do processo Collatz, independentemente do número que você entra. Como resultado, ele reconheceu que as técnicas para estudar PDEs poderiam ser aplicadas à conjectura de Collatz.
Uma método particularmente útil envolve uma maneira estatística de estudar o comportamento a longo prazo de um pequeno número de valores iniciais (como um pequeno número de configurações iniciais da água em uma lagoa) e extrapolar daí para o comportamento a longo prazo de todas as possíveis configurações iniciais da lagoa.
Se quase 100% dos números da amostra terminarem exatamente em 1 ou muito próximo a 1, você poderá concluir que quase todos os números se comportarão da mesma maneira.
Mas para que a conclusão seja válida, você precisará construir sua amostra com muito cuidado, não basta pegar uma porção de números aleatórios. O desafio é semelhante a gerar uma amostra de eleitores em uma pesquisa presidencial. Para extrapolar com precisão da pesquisa para a população como um todo, você precisará ponderar a amostra com a proporção correta de conservadores e progressistas, mulheres e homens, e assim por diante.
Como as pessoas, os números têm suas próprias características "demográficas". Existem números ímpares e pares, é claro, e números múltiplos de 3 e números que diferem entre si de maneiras ainda mais sutis. Quando você constrói uma amostra de números, pode ponderá-la para conter certos tipos de números e não outros - e quanto melhor você escolher seus pesos, mais precisamente poderá tirar conclusões sobre os números como um todo.
O desafio de Tao foi muito mais difícil do que apenas descobrir como criar uma amostra inicial de números com os pesos adequados. Em cada etapa do processo Collatz, os números com os quais você trabalha mudam. Uma mudança óbvia é que quase todos os números da amostra ficam menores.
Outra mudança, talvez menos óbvia, é que os números podem começar a se agrupar. Por exemplo, você pode começar com uma distribuição uniforme e agradável, como os números de 1 a 1 milhão. Porém, cinco iterações da Collatz depois, é provável que os números se concentrem em alguns pequenos intervalos na linha numérica. Em outras palavras, você pode começar com uma boa amostra, mas cinco etapas depois é irremediavelmente distorcida.
Talvez a principal contribuição de Tao foi descobrir como escolher uma amostra de números que, em grande parte, mantém seus pesos originais durante todo o processo de Collatz.
Por exemplo, a amostra inicial do Tao é ponderada para não conter múltiplos de 3, pois, de qualquer forma, o processo de Collatz elimina rapidamente múltiplos de 3. Já alguns dos outros pesos que o Tao criou são mais complicados. Ele pesa sua amostra inicial em números que tenham um restante de 1 depois de serem divididos por 3 e se afastam de números que têm um restante de 2 depois de serem divididos por 3.
O resultado é que a amostra com a qual o Tao começa mantém seu caráter, à medida que o processo Collatz prossegue.
Tao usou essa técnica de ponderação para provar que quase todos os valores iniciais de Collatz - 99% ou mais - finalmente atingem um valor bastante próximo de 1. Isso permitiu que ele tirasse conclusões ao longo das linhas de 99% dos valores iniciais superiores a 1 quadrilhão eventualmente atingir um valor abaixo de 200.
É sem dúvida o resultado mais forte da longa história da conjectura.
Experimente
Regras da sequência – Dado um número inteiro positivo inicial:
Mas afinal, vale a pena resolver? (Atualização)
Aparentemente a sequência leva sempre ao mesmo ponto, não importa como se inicia.
Mas a confusão é tamanha na hora de resolvê-lo desenhando um algoritmo (sequência finita de regras, raciocínios ou operações que permite solucionar classes semelhantes de problemas), que a distribuição das soluções já foi compara com graniza. Uma vez que, como o granizo nas nuvens antes de cair, os números saltam de um lugar ao outro antes de chegar ao 4, 2, 1, sem sentido aparente.
Apesar de simples de entender é quase impossível provar. Então, fica a questão: Vale a pena resolvê-lo?
Também há um motivo mais imediato especialmente direcionado aos não iniciados nesse trabalho de Sísifo de busca de regularidades e padrões.
Fonte: Quanta Magazine, Imagem (adaptada de) XKCD, BBC Brasil
[Visto no Brasil Acadêmico]
Parece o enunciado de um truque de mentalismo: Escolha um número, qualquer número inteiro positivo. Se for par, reduza para metade. Se for ímpar, multiplique por 3 e adicione 1. Repita. Todos os números iniciais levam a 1?
A conjectura é justamente sobre o que acontece se você continuar repetindo o processo. Intuitivamente podemos achar que o número com o qual você começa acabe afetando o número com o qual você termina. Alguns números talvez cheguem a 1. Outros talvez continuem em uma sucessão infinita de cálculos. (No final do post há uma calculadora para você calcular a série a partir de um número inteiro positivo).
Lothar Collatz provavelmente apresentou sua conjectura na década de 1930. previu que não é esse o caso. Ele conjecturou que, se você começar com um número inteiro positivo e executar esse processo por tempo suficiente, todos os valores iniciais levarão a 1. E quando você chegar a 1, as regras da conjectura de Collatz farão você entrar em um ciclo repetitivo para sempre: 1, 4, 2, 1, 4, 2, 1...
“A matemática não está pronta para este tipo de problema.”
Paul Erdős. Matemático. Sobre a conjectura de Colltz.
Ao longo dos anos, foram muitos os que se deixaram seduzir por essa espécie de "caneta azul" matemática. Um chiclete mental aparentemente inocente e provavelmente inútil. Sua simplicidade fez inúmero matemáticos e entusiastas da matemática literalmente perderem tempo tentando resolver o problema "3x + 1". Como também é conhecido.
Mas é possível encontrá-lo como conjectura de Ulam (pelo matemático polonês-americano Stanislaw Marcin Ulam), problema de Kakutani (pelo matemático nipo-americano Shizuo Kakutani), conjectura de Thwaites (pelo acadêmico britânico Bryan Thwaites), algoritmo de Hasse (pelo matemático alemão Helmut Hasse) ou problema de Siracusa.<br/>Trecho de matéria da BBC sobre o problema.
“Você só precisa saber multiplicar por 3 e dividir por 2 e pode começar a brincar imediatamente. É muito tentador.”
Marc Chamberland. Matemático do Grinnell College que produziu um popular vídeo no YouTube sobre o problema chamado “O Problema Mais Simples e Impossível” (“The Simplest Impossible Problem”).
Foram testados quintilhões de exemplos (18 zeros) sem encontrar uma única exceção à previsão de Collatz. A Internet está repleta de provas amadoras infundadas que afirmam ter resolvido o problema de uma alguma forma.
“Este é um problema realmente perigoso. As pessoas ficam obcecadas com isso e é realmente impossível.”
Jeffrey Lagarias. Matemático e professor na Universidade de Michigan. Autor do livro “The Ultimate Challenge: The 3 x + 1 Problem” e há 40 anos intrigado com a conjectura de Collatz
Na década de 1970, matemáticos mostraram que quase todas as seqüências de Collatz - a lista de números que você obtém ao repetir o processo - chegam a um número menor do que onde você começou - evidências consideradas fracas de que quase todas as sequências de Collatz se inclinam para 1.
“Collatz é um problema notoriamente difícil - tanto que os matemáticos tendem a anteceder todas as discussões sobre o assunto com um aviso para não perder tempo trabalhando nele.” Joshua Cooper. Professor da Universidade da Carolina do Sul
Finalmente, uma novidade
Terence Tao não é do tipo que fica investindo tempo em problemas fúteis. Em 2006, ele ganhou a Medalha Fields, a maior honra da matemática, e ele é amplamente considerado como um dos principais matemáticos de sua geração. Ele está acostumado a resolver problemas, não a perseguir delírios.
Todavia, Tao não resiste inteiramente aos cantos das sereias de seu campo de atuação. Todos os anos, ele se arrisca por um dia ou dois em algum dos famosos problemas ainda não resolvidos da matemática. Ao longo dos anos, ele fez algumas tentativas para resolver a conjectura de Collatz, sem sucesso.
 | ||
| Granizo: Passos necessárias para chegar a 4, 2, 1 para os números de 2 a 10.000.000 |
Eu não respondi, mas isso me fez pensar sobre o problema novamente.
Terence Tao. Matemático ganhador da medalha Fields em 2006
E fo aí que ele notou que a conjectura de Collatz era semelhante, em alguma medida, aos tipos de equações - chamadas equações diferenciais parciais (PDE, na sigla em inglês) - que apareceram em alguns dos resultados mais significativos de sua trajetória.
As PDEs podem ser usadas para modelar muitos dos processos físicos mais fundamentais do universo, como a evolução de um fluido ou a ondulação da gravidade no espaço-tempo. Elas surgem em situações em que a posição futura de um sistema - como o estado de uma lagoa 5 segundos após de você atirar uma pedra nela - depende de contribuições de dois ou mais fatores, como a viscosidade e a velocidade da água.
Apesar de PDEs complicadas não parecerem ter muito a ver com uma pergunta simples sobre aritmética como a conjectura de Collatz, Tao percebeu que havia algo semelhante neles. Com um PDE, você conecta alguns valores, obtém outros valores e repete o processo - tudo para entender esse estado futuro do sistema. Para qualquer PDE, os matemáticos querem saber se alguns valores iniciais acabam levando a valores infinitos como saída ou se uma equação sempre produz valores finitos, independentemente dos valores com os quais você começa.
Para ele, esse objetivo tinha o mesmo sabor de investigar se você sempre obtém o mesmo número (1) do processo Collatz, independentemente do número que você entra. Como resultado, ele reconheceu que as técnicas para estudar PDEs poderiam ser aplicadas à conjectura de Collatz.
Uma método particularmente útil envolve uma maneira estatística de estudar o comportamento a longo prazo de um pequeno número de valores iniciais (como um pequeno número de configurações iniciais da água em uma lagoa) e extrapolar daí para o comportamento a longo prazo de todas as possíveis configurações iniciais da lagoa.
No contexto da conjectura de Collatz, imagine começar com uma grande amostra de números. Seu objetivo é estudar como esses números se comportam quando você aplica o processo Collatz.
Se quase 100% dos números da amostra terminarem exatamente em 1 ou muito próximo a 1, você poderá concluir que quase todos os números se comportarão da mesma maneira.
Mas para que a conclusão seja válida, você precisará construir sua amostra com muito cuidado, não basta pegar uma porção de números aleatórios. O desafio é semelhante a gerar uma amostra de eleitores em uma pesquisa presidencial. Para extrapolar com precisão da pesquisa para a população como um todo, você precisará ponderar a amostra com a proporção correta de conservadores e progressistas, mulheres e homens, e assim por diante.
Como as pessoas, os números têm suas próprias características "demográficas". Existem números ímpares e pares, é claro, e números múltiplos de 3 e números que diferem entre si de maneiras ainda mais sutis. Quando você constrói uma amostra de números, pode ponderá-la para conter certos tipos de números e não outros - e quanto melhor você escolher seus pesos, mais precisamente poderá tirar conclusões sobre os números como um todo.
O desafio de Tao foi muito mais difícil do que apenas descobrir como criar uma amostra inicial de números com os pesos adequados. Em cada etapa do processo Collatz, os números com os quais você trabalha mudam. Uma mudança óbvia é que quase todos os números da amostra ficam menores.
Outra mudança, talvez menos óbvia, é que os números podem começar a se agrupar. Por exemplo, você pode começar com uma distribuição uniforme e agradável, como os números de 1 a 1 milhão. Porém, cinco iterações da Collatz depois, é provável que os números se concentrem em alguns pequenos intervalos na linha numérica. Em outras palavras, você pode começar com uma boa amostra, mas cinco etapas depois é irremediavelmente distorcida.
Talvez a principal contribuição de Tao foi descobrir como escolher uma amostra de números que, em grande parte, mantém seus pesos originais durante todo o processo de Collatz.
Você pode ficar obcecado com esses grandes problemas famosos que estão muito além da capacidade de qualquer um tocar e pode perder muito tempo.
Terence Tao. Matemático
Por exemplo, a amostra inicial do Tao é ponderada para não conter múltiplos de 3, pois, de qualquer forma, o processo de Collatz elimina rapidamente múltiplos de 3. Já alguns dos outros pesos que o Tao criou são mais complicados. Ele pesa sua amostra inicial em números que tenham um restante de 1 depois de serem divididos por 3 e se afastam de números que têm um restante de 2 depois de serem divididos por 3.
O resultado é que a amostra com a qual o Tao começa mantém seu caráter, à medida que o processo Collatz prossegue.
Tao usou essa técnica de ponderação para provar que quase todos os valores iniciais de Collatz - 99% ou mais - finalmente atingem um valor bastante próximo de 1. Isso permitiu que ele tirasse conclusões ao longo das linhas de 99% dos valores iniciais superiores a 1 quadrilhão eventualmente atingir um valor abaixo de 200.
É sem dúvida o resultado mais forte da longa história da conjectura.
Experimente
Regras da sequência – Dado um número inteiro positivo inicial:
- Se o número é par, dividir por 2
- Se é ímpar, multiplicar por 3 e somar 1
- Repita os passos acima com o resultado até atingir 1
Sequência de Collatz
Mas afinal, vale a pena resolver? (Atualização)
Aparentemente a sequência leva sempre ao mesmo ponto, não importa como se inicia.
Mas a confusão é tamanha na hora de resolvê-lo desenhando um algoritmo (sequência finita de regras, raciocínios ou operações que permite solucionar classes semelhantes de problemas), que a distribuição das soluções já foi compara com graniza. Uma vez que, como o granizo nas nuvens antes de cair, os números saltam de um lugar ao outro antes de chegar ao 4, 2, 1, sem sentido aparente.
Apesar de simples de entender é quase impossível provar. Então, fica a questão: Vale a pena resolvê-lo?
"Os matemáticos suspeitam que solucionar a conjectura de Collatz abrirá novos horizontes e desenvolverá novas e importantes técnicas na teoria dos números."
Dr. Greg Muller. Universidade de Oklahoma
Também há um motivo mais imediato especialmente direcionado aos não iniciados nesse trabalho de Sísifo de busca de regularidades e padrões.
"Outra razão é que, por ser fácil de apresentar e entender, tem potencial de atrair jovens para a matemática. Eu mesmo soube de sua existência no ensino médio e não resisti a seu encanto". Derek Jennings. Matemático
Fonte: Quanta Magazine, Imagem (adaptada de) XKCD, BBC Brasil
[Visto no Brasil Acadêmico]
Se alguém resolver, será que poderá ter influência social, a partir disso?
ResponderExcluirSe alguém resolver, será que poderá ter positiva influência social, a partir disso?
ResponderExcluir