Collatz che tende ad 1

Altro giochino matematico (questo ve lo ricordate?)… prima di dirvi che rimane una delle congetture più inafferrabili della matematica.

Prendiamo un numero a caso, intero e maggiore di 1. Se il numero è pari dividiamo per due, mentre se è dispari moltiplichiamo per tre ed aggiungiamo uno. Algebricamente facciamo:

collatz1.png

Mi sembra abbastanza semplice, proviamo con 11. Tanto per tirare un numero a caso…

Prendiamo il numero risultante e riapplichiamo la regola. Che succede secondo voi?

Allora:

  • 11 è dispari, quindi faccio: 11*3+1 = 34
  • 34 è pari, quindi faccio: 34/2 = 17
  • 17 è dispari, quindi faccio: 17*3+1 = 52
  • 52 è pari, qundi faccio: 52/2 = 26

Avete l’impressione che stiamo divergendo? Che stiamo ottenendo numeri a caso? Ottimo, continuiamo.

  • 26 è pari, quindi faccio: 26/2 = 13
  • 12 è dispari, quindi faccio: 12*3+1 = 40
  • 40 è pari, quindi faccio: 40/2 = 20
  • 20 è pari, quindi faccio: 20/2 = 10
  • 10 è pari, quindi faccio: 10/2 = 5
  • 5 è dispari, quindi faccio: 5*3+1 = 16
  • 16 è pari, quindi faccio: 16/2 = 8
  • 8 è pari, quindi faccio: 8/2 = 4
  • 4 è pari, quindi faccio: 4/2 = 2
  • 2 è pari, quindi faccio: 2/2 = 1

Il fatto che abbia raggiunto 1 è un caso? Che succede se applica l’algoritmo ad 1?

  • 1 è dispari, quindi faccio: 1*3+1 = 4
  • 4 è pari, quindi faccio: 4/2 = 2
  • 2 è pari, quindi faccio: 2/2 = 1

torno ad 1. Effettivamente in alcuni enunciati dell’algoritmo si pone anche come condizione di stop quando la serie raggiunge 1.

Ora la domanda, da molti milioni di dollaroni, è, ma si raggiunge sempre 1 o esiste qualche numero (magari con qualche decina di cifre, tanto per essere ultra-difficile da scovare…) per cui ciò non è vero? Beh, la risposta è, come nelle migliori tradizioni, non lo sappiamo.

Esatto, siamo di fronte alla congettura di Colaltz.

Non esiste una dimostrazione matematica che si finisce sempre con l’ottenere 1 (che come abbiamo visto ritorna ad uno nel giro di tre iterazioni), ma è stata provata numericamente (al pc, per intenderci) fino a circa 1 x 10^20… un numero decisamente grande da lasciare qualche dubbio che il primo contro-esempio possa essere ancora maggiore…

Inoltre, un po’ ad occhio, l’algoritmo dimezzando i numeri pari e facendo *3+1 con i dispari aumenta solo i dispari di un fattore circa 3/4, quindi vi sono buone speranze che questi decrescano verso 1.

Per farla breve: ci crediamo tanto ed effettivamente abbiamo buone ragioni per farlo, ma dimostrare matematicamente che sappiamo come finisce questo giochino in tutti i casi possibili ed immaginabili non è alla nostra portata.

La matematica non è ancora pronta per problemi di questo tipo [Paul Erdős, matematico, circa questa congettura]

WU

PS. Sotto un po di fury computations (si, ho fatto uno stupido foglio excel fare giocare… peto venia) con tre esempi dell’andamento dei valori per 11, 367 ed 888.
L’andamento ed i valori raggiunti dalla successione variano sostanzialmente, ma il destino unitario rimane lo stesso.

collatz2.png

Rispondi

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

Logo di WordPress.com

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

Google photo

Stai commentando usando il tuo account Google. 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 )

Connessione a %s...