Network Bar

giovedì 6 ottobre 2011

La congettura di Collatz inversa.

Scegliete un numero (intero e positivo, e così sarà per qualsiasi "numero" nel post). Se pari, dividetelo per 2; se dispari, moltiplicatelo per 3 e sommategli 1. Ora ricominciate da capo ripetendo l'operazione con il numero che avete ottenuto.

La congettura di Collatz, che prende il nome dal matematico tedesco Lothar Collatz che l'ha proposta nel 1937, afferma che qualsiasi sia il numero scelto in principio il risultato finale di un numero finito di iterazioni della procedura descritta sopra è 1.

La congettura è celebre perché è tanto semplice da formulare quanto, sembrerebbe, difficile da dimostrare. Il condizionale è d'obbligo perché una dimostrazione - per i pessimisti un controesempio - alla congettura ancora non è stata data. Molti matematici, professionisti e dilettanti, si sono cimentati nell'impresa ma, utilizzando le parole di Terence Tao

[...] Open questions with this level of notoriety can lead to what Richard Lipton calls "mathematical diseases” (and what I termed an unhealthy amount of obsession on a single famous problem). [...] As such, most practicing mathematicians tend to spend the majority of their time on more productive research areas that are only just beyond the range of current techniques. [...]
Della stessa opinione Randall Munroe, qualche tempo fa, con una vignetta su xkcd

Collatz Conjecture

Via Flowing Data scopro che tra i vari approcci e tecniche di dimostrazione c'è quello inverso: invece che partire da un qualsiasi numero ed arrivare ad 1 attraverso l'iterazione finita del procedimento di sopra perchè non partire da 1 ed arrivare per mezzo di un procedimento inverso ad ogni numero? Il risultato di questo procedimento inverso si chiama grafo di Collatz; si può dimostrare (provateci ;-) ) che la congettura di Collatz è equivalente al fatto che tale grafo esiste e che è un albero, ovvero è connesso e non ammette cicli, a meno di quello triviale 1-2-4 (per i dettagli rimando alla wiki-pagina). Jason Davies, programmatore e web disegner britannico, riesce ad animare la congettura inversa attraverso uno script in python che fa crescere il grafo di Collatz per traiettorie (o orbite) di lunghezza inferiore o uguale a 18. Merita un play!

P.s. gli amanti dei demonstration project di Wolfram trovano qui l'omologo (ma più pesante) file .cdf

4 commenti:

  1. Non conoscevo questa congettura! E' stupefacente che nessuno sia ancora riuscito a dimostrarla, sembra una cosa così banale in apparenza :-)

    RispondiElimina
  2. Neppure io la conoscevo... Concordo con Moreno!

    RispondiElimina
  3. In fondo anche il famoso ultimo teorema di Fermat sembrava facile da dimostrare, ma ci sono voluti un po' di secoli (e di calcoli!)

    RispondiElimina
  4. Ieri mi sono divertita a creare un file di excel con i numeri da 1 a 100!
    https://docs.google.com/spreadsheet/ccc?key=0AimxRFlD3q9VdGU1bzlqMEFkbHFxeXlSTktNOEIzcFE&hl=it

    RispondiElimina