La congettura di Collatz (3x + 1) pt. 1

Ehilà gente!

Oggi piccola riflessione su uno dei problemi che ha smosso il mondo intero nel dopoguerra: La congettura di Collatz

Da alcuni fu anche teorizzato che questo problema fu inventato dai sovietici per rallentare la ricerca americana

Ma per ora siamo troppo impegnati in queste cose...

- - - - - - - - -

Prima di tutto però, cos'è la congettura di Collatz?

Ve lo spiego subito

Prendiamo un numero casuale, 7

È dispari, quindi lo moltiplichiamo per 3 e aggiungiamo 1

(3 · 7) + 1 = 22

Ora è pari, quindi lo dividiamo per 2

22 / 2 = 11

Dispari, moltiplico per 3 e aggiungo 1

(3 · 11) + 1 = 34

Pari

34 / 2 = 17

(3 · 17) + 1 = 52

52 / 2 = 26

26 / 2 = 13

(3 · 13) + 1 = 40

40 / 2 = 20

20 / 2 = 10

10 / 2 = 5

(3 · 5) + 1 = 16

16 / 2 = 8

8 / 2 = 4

4 / 2 = 2

2 / 2 = 1

Ora di nuovo

(3 · 1) + 1 = 4

4 / 2 = 2

2 / 2 = 1

E quindi ci chiudiamo in un ciclo chiuso

Diciamo quindi che 7, con questo algoritmo, arriva a 1 in 16 passaggi

Proviamo con altri numeri, come 9, 15, 102

Ma tutti sembrano arrivare a 1, prima o poi

La congettura di Collatz dice che:

Ogni numero naturale, se applicato questo algoritmo, arriva a 1

Bella scommessa eh?

Impossibile da computare manualmente, dato che ci sono infiniti numeri naturali

Quindi, ecco il mio ragionamento:

Visualizziamo l'algoritmo, prendendo un certo numero x

Se pari lo divido per 2 ( x / 2 )

Se dispari lo moltiplico per 3, aggiungo 1 e divido per 2 ( ( 3x + 1 ) / 2 )

Essendo che ogni numero della forma 3x + 1 è pari, e dunque includo già il passaggio precedente

Creiamo un albero di possibilità

Notiamo come abbiamo 3 casi generali:

1. Il più a sinistra, i numeri si alternano per sempre tra pari e dispari

2. Il più a destra, i numeri sono sempre pari, e quindi non arrivano mai a 1

   
   

3. Un caso nel mezzo, in cui i numeri si alternano tra pari e dispari con o senza periodicità

Se andiamo ad esplicitare il caso 1, possiamo scrivere:

A1 = x

A2 = ( 3x + 1 ) / 2

A3 = ( 3 · ( ( 3x + 1 ) / 2 ) + 1 ) / 2

E così via, con A che rappresenta lo step corrispondente (A1 = step 1, A2 = step 2, ...)

Notiamo che possiamo riscrivere, per esempio, A3, come:

A3 = ( ( 3 · A2 ) + 1 ) / 2

E possiamo generalizzare questa congruenza per tutti gli step successivi Aₙ

A[n] = ( ( 3 · A[n-1] ) + 1 ) / 2

E considerando il passaggio infinito (quando l'algoritmo si trova in un ciclo infinito diverso da 4 2 1)

A[∞] = ( ( 3 · A[∞-1] ) + 1 ) / 2

A[∞] = ( ( 3 · A[∞] ) + 1 ) / 2 (Dato che ∞ - 1 = ∞)

Sostituendo A[∞] con x:

x = ( 3x + 1 ) / 2

2x = 3x + 1

-x = 1

x = -1

E dovendo considerare solo valori di x naturali ( x∈N )

Non esiste valore di x tale che si alterni tra pari e dispari con ciclicità 1 ("una volta si una volta no" per come diremmo noi in italiano)

Quindi possiamo escludere il caso 1, valutandolo impossibile

Passiamo ora al caso 2, con lo stesso ragionamento:

A1 = x

A2 = x / 2          (Pari)

A3 = ( x / 2 ) / 2          (Sempre pari)

...

Vale quindi:

A[n] = ( A[n-1] ) / 2

A[∞] = ( A[∞-1] ) / 2

x = x / 2

2x = x

x = 0

Non accettabile poichè non naturale ( N = { 1, 2, 3, 4, ... } )

Quindi anche questo caso va escluso

Ci restano quindi solo i casi generali...

... che andremo a trattare nei prossimi post, chiaramente!

- - - - - - - - -

Per ora ci siamo solo scaldati, fidatevi

Questo problema è assurdo

Ma è questo il bello no?

Prendere problemi incredibili

E spezzettarli...

Gente, io vi saluto e vi auguro un buon proseguimento...

Al prossimo post