La congettura di Collatz: il problema che fa perdere tempo ai matematici

La congettura di Collatz è un problema matematico irrisolto che sembra un gioco di magia: scegli un numero a caso, se è dispari moltiplicalo per 3 ed aggiungi 1, se è pari dimezzalo, poi ripeti la procedura tante volte: scommettiamo che prima o poi arriverai a 1? Questa congettura fu proposta da Lothar Collatz nel 1937 ed è ancora irrisolta. Negli ultimi anni è diventata piuttosto popolare nel mondo dei social, ma è famosa anche in ambito accademico, tanto che il matematico Paul Erdős offrì 500 dollari per chi la risolvesse. Vediamo in cosa consiste il problema, perché lo chiamiamo congettura e come stanno andando i tentativi di risoluzione, ma stabiliremo anche un nostro piccolo record al riguardo.

Cosa dice la congettura di Collatz

Prima di tutto, che cos'è una congettura? In matematica una congettura è un’affermazione che pensiamo possa essere vera, ma per la quale non si conosce nessuna dimostrazione. In pratica supponiamo che sia vera perché così ci dice l'esperienza, ma dato che nessuno è riuscito a trovare la prova di tale verità rimaniamo aperti all’eventualità che alla fine si riveli falsa. Risolvere la congettura significa stabilire definitivamente se è vera oppure falsa.

La congettura di Collatz sembra all'apparenza estremamente semplice, eppure ancora non conosce dimostrazione. Funziona così, si parte con un numero intero e ci si chiede se è pari o dispari:

1. se il numero è pari lo si divide per 2
2. se invece è dispari lo si moltiplica per 3 e al risultato e si aggiunge 1

Ripetendo questa procedura "all'infinito", la congettura afferma che prima o poi arriveremo ad avere come risultato 1. E se proseguiamo ulteriormente da 1, di nuovo avremo 1 come risultato. Facciamo un esempio.

Partiamo con il numero 5 e ripetiamo la procedura con ogni risultato che otteniamo:

• 5 è dispari, quindi secondo la regola lo moltiplichiamo per 3 e aggiungiamo 1 ottenendo il risultato 5×3 + 1= 15 + 1 = 16
• 16 è pari, quindi lo dividiamo per 2 ottenendo 16÷2 = 8
• 8 è pari, quindi proseguendo abbiamo 8÷2 = 4
• 4 è pari, quindi abbiamo 4÷2 = 2
• 2 è pari, ed ecco che arriviamo arriviamo fino ad 1, cioè 2÷2

Siamo arrivati proprio a 1, come avevamo congetturato! O meglio, come ha congetturato Collatz. Se ora proviamo a proseguire una volta arrivati a 1:

• 1 è dispari, lo moltiplichiamo per 3 e aggiungiamo 1 ottenendo di nuovo 4
• da 4 si passa a 2, come abbiamo già visto
• da 2 si passa a 1, e così via. Si è creato un ciclo, da 1 non si scappa più!

Allora ci si può chiedere: se partiamo da un qualsiasi numero diverso da 5, cadremo comunque in questo ciclo infinito? Raggiungiamo comunque 1 e poi non ne scappiamo più?

Secondo Collatz, partendo da un numero qualsiasi, prima o poi, approdiamo al numero 1, solo che nessuno è riuscito a provarlo: in pratica pensiamo che sia vero, ma non ne siamo sicuri al 100%. Potete però provare con qualsiasi numero di partenza e vedrete che arriverete a 1. Se così non fosse… beh complimenti! Avreste trovato la primissima controprova della congettura e diventereste famosi nel mondo della matematica.

I tentativi di risoluzione della congettura

Ora che conoscete la congettura potete prendere carta, penna e calcolatrice e provare in prima persona a verificarne la veridicità, ma fate attenzione perché secondo il matematico Terence Tao – vincitore della medaglia Fields nel 2006, una specie di Nobel della matematica – si tratta di

Una delle congetture più “pericolose”, famosa aver assorbito enormi quantità di tempo sia da parte di matematici professionisti che dilettanti

Insomma, sebbene la congettura di Collatz sembri effettivamente vera, neanche i migliori matematici del mondo sono ancora riusciti a dimostrarla! Quindi non fatevi ingannare, questa congettura è diventata piuttosto popolare sui social e può capitare di imbattersi in utenti dei vari social che affermano di essere riusciti a risolverla, ma al momento non ci è ancora riuscito nessuno.

In molti ci hanno provato e il matematico Shizuo Kakutani, nel 1960, affermò che per circa un mese all’università di Yale tutti lavorarono alla congettura, senza risultati. Lo stesso accadde all’università di Chicago, così che iniziò a circolare, come battuta, l’idea che la congettura di Collatz facesse parte di una cospirazione per rallentare il lavoro dei matematici statunitensi.

I tentativi di risoluzione: cercare l'errore

Tra i tentativi di risolvere la congettura vale la pena citare le prove empiriche in cui, più che cercare una dimostrazione rigorosa, si cerca piuttosto l'esistenza di un numero che – prima o poi – invalidi la congettura. Basterebbe infatti trovare un solo numero per il quale, reiterando la procedura che abbiamo descritto, non si arriva mai al numero 1.

Ad oggi, la congettura è risultata valida per tutti i numeri fino a 2.361.183.241.434.822.606.848 (ovvero 2⁷¹ ), per cui se avete intenzione di cercare dei numeri per cui non funziona dovreste partire da numeri più alti di questo. Noi lo abbiamo fatto per il numero successivo, cioè 2⁷¹+1 =  2.361.183.241.434.822.606.849: dopo soli 3 passaggi applicando la regola della congettura, il risultato scende sotto 2⁷¹, per cui possiamo affermare che anche il numero successivo verifica la congettura.

Ovviamente nessuno potrebbe mai riuscire a testare la congettura su tutti numeri possibili ed immaginabili, visto che sono infiniti, quindi se vogliamo dimostrare che la congettura è vera bisogna seguire altre strade, ma non è così facile, come sancito da Paul Erdos nel 1983 che affermò

la matematica non è ancora matura per problemi di questo tipo.

Sono passati alcuni decenni ed ancora non sappiamo risolvere completamente questo problema nonostante studi di vario genere, tra cui quello di Conway che ha creato un linguaggio di programmazione, il FRACTRAN, basato sulle regole della congettura di Collatz con il quale si può eseguire qualunque operazione si possa eseguire con un computer.

I risultati più recenti sono quelli di Tao che, migliorando il lavoro di altri matematici che lo hanno preceduto, è stato in grado di dimostrare che la congettura è vera per “quasi tutti” i numeri (qualcosa tipo il 99,99% dei numeri) …ma quasi tutti i numeri non sono tutti i numeri.

non perderti questo video

Il paradosso di Monty Hall: la spiegazione del gioco delle tre porte e il calcolo delle probabilità