Il semplice problema di matematica che ancora non possiamo risolvere
Questa colonna viene fornita con un avviso: non tentare di risolvere questo problema di matematica.
Sarai tentato. Questo problema è semplicemente enunciato, facilmente comprensibile e fin troppo invitante. Scegli un numero, un numero qualsiasi: se il numero è pari, taglialo a metà; se è dispari, triplicalo e aggiungi 1. Prendi quel nuovo numero e ripeti il processo, ancora e ancora. Se continui così, alla fine rimarrai bloccato in un loop. Almeno, è quello che pensiamo accadrà.
Prendi 10 per esempio: 10 è pari, quindi lo tagliamo a metà per ottenere 5. Dato che 5 è dispari, triplichiamo e aggiungiamo 1. Ora abbiamo 16, che è pari, quindi lo dimezziamo per ottenere 8, quindi dimezziamo che per ottenere 4, quindi dimezzarlo di nuovo per ottenere 2, e ancora una volta per ottenere 1. Dato che 1 è dispari, triplichiamo e aggiungiamo 1. Ora siamo di nuovo a 4, e sappiamo dove va: 4 va a 2 che va a 1 che va a 4 e così via. Siamo bloccati in un loop.
Oppure prova 11: è strano, quindi triplichiamo e aggiungiamo 1. Ora abbiamo 34, che è pari, quindi lo dimezziamo per ottenere 17, lo triplichiamo e aggiungiamo 1 per ottenere 52, dimezziamo quello per ottenere 26 e di nuovo per ottenere 13, triplicalo e aggiungi 1 per ottenere 40, dimezzalo per ottenere 20, poi 10, quindi 5, triplo e aggiungi 1 per ottenere 16 e dimezzalo per ottenere 8, poi 4, 2 e 1. E noi siamo bloccato di nuovo nel ciclo.
La famigerata congettura di Collatz dice che se inizi con un numero intero positivo, finirai sempre in questo ciclo. E probabilmente ignorerai il mio avvertimento sul tentativo di risolverlo: sembra troppo semplice e troppo ordinato per resistere alla comprensione. In effetti, sarebbe difficile trovare un matematico che non abbia giocato con questo problema.
Non potevo ignorarlo quando l'ho saputo per la prima volta a scuola. I miei amici e io abbiamo passato giorni e giorni a scambiare idee elettrizzanti che non sembravano mai avvicinarci a una risposta. Ma la congettura di Collatz è famigerata per una ragione: anche se ogni numero che è mai stato provato finisce in quel ciclo, non siamo ancora sicuri che sia sempre vero. Nonostante tutta l'attenzione, è ancora solo una congettura.
Eppure sono stati compiuti progressi. Uno dei più grandi matematici viventi del mondo ha ignorato tutti gli avvertimenti e ha fatto un tentativo, facendo i maggiori passi avanti sul problema da decenni. Diamo un'occhiata a cosa rende questo semplice problema così complicato.
Per comprendere la congettura di Collatz, inizieremo con la seguente funzione:
$ latex f (n) = begin {case}
n / 2 & text {se $ n $ è pari} \
3n + 1 & text {se $ n $ è dispari}
end {case} $
Potresti ricordare le funzioni "a tratti" della scuola: la funzione precedente accetta un input n e applica ad esso una delle due regole, a seconda che l'input sia dispari o pari. Questa funzione f attua le regole della procedura che abbiamo descritto sopra: Ad esempio, f (10) = 10/2 = 5 poiché 10 è pari e f (5) = 3 × 5 + 1 = 16 poiché 5 è dispari. A causa della regola per gli input dispari, la congettura di Collatz è anche conosciuta come congettura 3 n + 1.
La congettura di Collatz si occupa delle “orbite” di questa funzione f . Un'orbita è ciò che ottieni se inizi con un numero e applichi una funzione ripetutamente, prendendo ogni output e reinserendolo nella funzione come un nuovo input. Chiamiamo questo "iterazione" della funzione. Abbiamo già iniziato a calcolare l'orbita di 10 sotto f , quindi troviamo i prossimi termini:
f (10) = 10/2 = 5
f (5) = 3 × 5 + 1 = 16
f (16) = 16/2 = 8
f (8) = 8/2 = 4
Un modo conveniente per rappresentare un'orbita è come una sequenza con le frecce. Ecco l'orbita di 10 sotto f :
10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …
Alla fine vediamo di essere bloccati nel loop 1 → 4 → 2 → 1 →….
Allo stesso modo, l'orbita per 11 sotto f può essere rappresentata come
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 →….
Ancora una volta finiamo nello stesso ciclo. Prova qualche altro esempio e vedrai che l'orbita sembra sempre stabilizzarsi in quel ciclo 4 → 2 → 1 →…. I valori iniziali di 9 e 19 sono divertenti e se hai qualche minuto libero, prova 27. Se la tua aritmetica è corretta, ci arriverai dopo 111 passaggi.
La congettura di Collatz afferma che l'orbita di ogni numero sotto f alla fine raggiunge 1. E mentre nessuno ha dimostrato la congettura, è stata verificata per ogni numero inferiore a 2 68 . Quindi, se stai cercando un controesempio, puoi iniziare circa 300 quintilioni. (Sei stato avvertito!)
È facile verificare che la congettura di Collatz sia vera per un numero particolare: calcola semplicemente l'orbita finché non arrivi a 1. Ma per vedere perché è difficile da dimostrare per ogni numero, esploriamo una funzione leggermente più semplice, ℊ .
$ latex g (n) = begin {case}
n / 2 & text {se $ n $ è pari} \
n + 1 & text {se $ n $ è dispari}
end {case} $
La funzione ℊ è simile ad f , ma per i numeri dispari aggiunge solo 1 invece di triplicarli prima. Poiché ℊ ef sono funzioni diverse, i numeri hanno orbite diverse sotto ℊ che sotto f . Ad esempio, ecco le orbite di 10 e 11 sotto ℊ :
10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …
11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …
Si noti che l'orbita di 11 raggiunge 1 più velocemente sotto ℊ che sotto f . Anche l'orbita di 27 raggiunge 1 molto più velocemente sotto ℊ.
27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …
In questi esempi, le orbite sotto ℊ sembrano stabilizzarsi, proprio come le orbite sotto f , ma in un ciclo leggermente più semplice:
→ 2 → 1 → 2 → 1 →….
Potremmo ipotizzare che le orbite sotto ℊ arrivino sempre a 1. La chiamerò congettura di "Nollatz", ma potremmo anche chiamarla congettura n + 1. Potremmo esplorarlo testando più orbite, ma sapere che qualcosa è vero per un mucchio di numeri – anche 2 68 di loro – non è una prova che sia vero per ogni numero. Fortunatamente, la congettura di Nollatz può essere effettivamente dimostrata. Ecco come.
Innanzitutto, sappiamo che metà di un numero intero positivo è sempre inferiore all'intero stesso. Quindi, se n è pari e positivo, allora ℊ ( n ) = n / 2 < n. In altre parole, quando un'orbita raggiunge un numero pari, il numero successivo sarà sempre più piccolo.
Ora, se n è dispari, allora ℊ ( n ) = n + 1 che è maggiore di n . Ma poiché n è dispari, n + 1 è pari, e quindi sappiamo dove andrà l'orbita: ℊ taglierà n + 1 a metà. Per uno strano n l'orbita sarà simile a questa:
… → n → n + 1 → $ latex frac {n + 1} {2} $ → …
Nota che $ latex frac {n + 1} {2} $ = $ latex frac {n} {2} $ + $ latex frac {1} {2} $. Dal momento che $ lattice frac {n} {2} $ <n e $ lattice frac {1} {2} $ è piccolo, $ lattice frac {n} {2} $ + $ lattice frac {1} {2 } $ è probabilmente anche minore di n . In effetti, una semplice teoria dei numeri può mostrarci che fintanto che n > 1, allora è sempre vero che $ latex frac {n} {2} $ + $ latex frac {1} {2} $ < n .
Questo ci dice che quando un'orbita sotto ℊ raggiunge un numero dispari maggiore di 1, saremo sempre a un numero minore due passi dopo. E ora possiamo delineare una prova della congettura di Nollatz: ovunque nella nostra orbita, che sia un numero pari o dispari, andremo verso il basso. L'unica eccezione è quando colpiamo 1 alla fine della nostra discesa. Ma una volta che abbiamo raggiunto 1, siamo intrappolati nel loop, proprio come abbiamo congetturato.
Può un argomento simile funzionare per la congettura di Collatz? Torniamo alla funzione originale.
$ latex f (n) = begin {case}
n / 2 & text {se $ n $ è pari} \
3n + 1 & text {se $ n $ è dispari}
end {case} $
Come con ℊ , l'applicazione di f a un numero pari lo riduce . E come con ℊ , l'applicazione di f a un numero dispari produce un numero pari, il che significa che sappiamo cosa succede dopo: f taglierà il nuovo numero a metà. Ecco come appare l'orbita sotto f quando n è dispari:
… → n → 3 n + 1 → $ latex frac {3n + 1} {2} $ → …
Ma qui è dove il nostro argomento va in pezzi. A differenza del nostro esempio sopra, questo numero è maggiore di n : $ latex frac {3n + 1} {2} $ = $ latex frac {3n} {2} $ + $ latex frac {1} {2} $, e $ latex frac {3n} {2} $ = 1.5 n , che è sempre maggiore di n . La chiave per la nostra dimostrazione della congettura di Nollatz era che un numero dispari deve finire più piccolo due passi dopo, ma questo non è vero nel caso di Collatz. Il nostro argomento non funzionerà.
Se sei come me e i miei amici a scuola, ora potresti essere entusiasta di provare che la congettura di Collatz è falsa: dopo tutto, se l'orbita continua a ingrandirsi, come può arrivare a 1? Ma questo argomento richiede di pensare a cosa accadrà dopo, e ciò che accadrà dopo chiarisce perché la congettura di Collatz è così sfuggente: non possiamo essere sicuri che $ latex frac {3n + 1} {2} $ sia pari o dispari.
Sappiamo che 3 n + 1 è pari. Se 3 n + 1 è anche divisibile per 4, anche $ latex frac {3n + 1} {2} $ è pari e l'orbita cadrà. Ma se 3 n + 1 non è divisibile per 4, allora $ latex frac {3n + 1} {2} $ è dispari e l'orbita aumenterà. In generale non possiamo prevedere quale sarà vero, quindi la nostra argomentazione si blocca.
Ma questo approccio non è del tutto inutile. Poiché la metà di tutti gli interi positivi sono pari, c'è una probabilità del 50% che $ latex frac {3n + 1} {2} $ sia pari, il che compie il passo successivo nell'orbita $ latex frac {3n + 1} {4 } $. Per n > 1 questo è minore di n , quindi la metà delle volte un numero dispari dovrebbe diminuire dopo due passaggi. C'è anche una probabilità del 50% che $ latex frac {3n + 1} {4} $ sia pari, il che significa che c'è una probabilità del 25% che un numero dispari venga ridotto a meno della metà di dove è iniziato dopo tre passaggi. E così via. Il risultato netto è che, in qualche modo medio, le orbite di Collatz diminuiscono quando incontrano un numero dispari. E poiché le orbite di Collatz diminuiscono sempre a numeri pari, ciò suggerisce che tutte le sequenze di Collatz devono diminuire nel lungo periodo. Questo argomento probabilistico è ampiamente noto, ma nessuno è stato in grado di estenderlo a una dimostrazione completa della congettura.
Eppure diversi matematici hanno dimostrato che la congettura di Collatz è "quasi sempre" vera. Ciò significa che hanno dimostrato che, rispetto alla quantità di numeri che sanno portare a 1, la quantità di numeri di cui non sono sicuri è trascurabile. Nel 1976 il matematico estone americano Riho Terras dimostrò che, dopo ripetute applicazioni della funzione di Collatz, quasi tutti i numeri alla fine finiscono più in basso rispetto al punto di partenza. Come abbiamo visto sopra, mostrare che i numeri nell'orbita si riducono costantemente è un modo per mostrare che alla fine arrivano a 1.
E nel 2019, Terence Tao , uno dei più grandi matematici viventi del mondo, ha migliorato questo risultato . Dove Terras ha dimostrato che per quasi tutti i numeri la sequenza di Collatz di n finisce sotto n , Tao ha dimostrato che per quasi tutti i numeri la sequenza di Collatz di n finisce molto più in basso: sotto $ latex frac {n} {2} $, sotto $ latex sqrt {n} $, sotto $ latex ln n $ (il logaritmo naturale di n ), anche sotto ogni f ( n ) dove f ( x ) è qualsiasi funzione che va all'infinito, non importa quanto lentamente. Cioè, per quasi ogni numero, possiamo garantire che la sua sequenza di Collatz vada tanto in basso quanto vogliamo. In un discorso sul problema , Tao ha detto che questo risultato è "il più vicino possibile alla congettura di Collatz senza risolverla".
Anche così, la congettura continuerà ad attrarre matematici e appassionati. Quindi scegli un numero, un numero qualsiasi e provalo. Ricorda solo che sei stato avvertito: non rimanere bloccato in un ciclo infinito.
Esercizi
1. Mostra che ci sono infiniti numeri le cui orbite di Collatz passano per 1.
2. Il "tempo di arresto" di un numero n è il numero minimo di passaggi necessari all'orbita di Collatz di n per raggiungere 1. Ad esempio, il tempo di arresto di 10 è 6 e il tempo di arresto di 11 è 14. Trova due numeri con tempo di arresto 5.
3. In un recente discorso sulla congettura di Collatz, Terrance Tao ha menzionato la seguente funzione simile a Collatz:
$ latex h (n) = begin {case}
n / 2 & text {se $ n $ è pari} \
3n-1 & text {se $ n $ è dispari}
end {case} $
Tao sottolinea che oltre al loop 1 → 2 → 1 → 2 → 1…, compaiono altri due loop. Li trovi?
Risposte
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all'URL https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/ in data Tue, 22 Sep 2020 15:40:56 +0000.