La congettura di Collatz

Visto il successo del post sul teorema della non pettinabilità della palla da tennis, ho pensato di inaugurare una miniserie.

E quindi oggi parliamo della Congettura di Collatz, perché non avevo capito la vignetta di xkcd e il proooof come sempre mi ha illuminato.

Cos’è la Congettura di Collatz? Un “giochino” semplice semplice, che dice: preso un numero intero positivo qualsiasi, se è pari lo dividiamo  per 2, se invece è dispari lo moltiplichiamo per 3 e aggiungiamo 1, e continuando così prima o poi arriviamo a 1 (da cui si entra in un ciclo: il numero successivo a 1 è 4, poi si ha 2, e di nuovo 1).

Per esempio:
11 (dispari) -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

E’ un gioco che si faceva spesso all’Università durante le ore di Campi elettromagnetici (bei tempi), e un algoritmo facile da implementare in qualsiasi linguaggio di programmazione  (tipo, dimostrare che la congettura di Collazt è vera per tutti gli interi minori o uguali a 1000).

Oppure durante una riunione noiosa, si parte dal primo numero citato dal relatore (“Questo mese abbiamo venduto 713 tonnellate in più del mese scorso…” e sotto a calcolare!).

E’ un giochino semplice nella sua formulazione, ma la congettura non è ancora stata dimostrata.

I tentativi per dimostrarla sono stati molti. Qualcuno ha pensato di dimostrare che la congettura non è vera trovando un controesempio (cioè un numero partendo dal quale la congettura risulta falsa). Ma finora non c’è ancora riuscito nessun calcolatore, e si che hanno tentato fino alla cifra 9·2^53.

Magari è più facile dimostrare che prima o poi si arriva sempre a un numero che è una potenza di 2, e da li si arriva subito a 1… ma sicuramente qualcuno ci ha già pensato.

Se volete provare, prego fatevi avanti: c’è un premio di 500 dollari offerto da Paul Erdős per il primo che dimostra la congettura. O forse c’era, visto che Erdős è scomparso nel 1996.

Per questo teorema (pardon, congettura) non ho trovato da nessuna parte qualche utilizzo pratico o qualche conseguenza rilevante: non serve assolutamente a niente, mica come pettinare le palle da tennis!

Però da una sua estensione nascono dei bei frattali:

Il frattale di Collatz

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...