martedì 12 giugno 2012

Intorno alla congettura di Collatz

Ogni tanto mi capita, lo devo ammettere. Son lì che devo far passare un po’ di tempo e sono lontano dal computer, ho carta e penna, allora prendo qualche numero di due cifre a caso e mi metto a giocare con la congettura di Collatz. Altri (ad esempio Roberto Zanasi o Maurizio Codogno) l’hanno trattata assai meglio di quanto io possa fare, pertanto mi limito a dire che si deve prendere un numero naturale qualsiasi n: se è pari. lo si divide per 2, se è dispari, lo si moltiplica per 3 e si aggiunge 1. Formalmente: 


Procedendo in questo modo, secondo il matematico tedesco Lothar Collatz, che se ne occupò per primo nel 1937, si arriva sempre a 1, magari dopo un percorso lunghissimo. Questa proprietà è stata verificata per numeri grandissimi (fino a un ordine di grandezza di 1018), ma non è mai stata dimostrata, ecco perché è una congettura e non un teorema. 

Da parte mia mi sono limitato a illustrare graficamente la soluzione per n ≤ 50, differenziando le decine con colori diversi nell'immagine qui sotto. Come si vede, se per numeri come 42 ce la si cava in 8 passaggi, il numero 27 richiede 111 passaggi prima di giungere a 1, un lungo serpentone di cifre che sale fino 9232 prima di scendere lentamente verso l’agognata unità. 




La congettura è stata descritta da R. Terras negli anni ’70 in una forma più economica, per la quale iterando


per un numero iniziale t0, si riduce il numero di passaggi per arrivare a 1. Operativamente, se n è dispari, lo si aumenta della metà e lo si arrotonda all'intero superiore. Così, ad esempio, se per 5 nella definizione di Collatz si hanno i passaggi 5, 16, 8, 4, 2, 1, in quella di Terras si ha 5, 8, 4, 2, 1. Per 27 si hanno 69 passaggi invece di 111. 



La versione di Terras della congettura ha ispirato nel 2006 alla poetessa matematica americana JoAnne Growney (che possiede un curriculum matematico di rispetto, avendo insegnato alla Bloomsburg University in Pennsylvania) dei versi che contengono un piccolo problema: 

A Mathematician's Nightmare 

Suppose a general store, 
items with unknown values 
and arbitrary prices 
rounded for ease to 
whole-dollar amounts. 

Each day Madame X, 
keeper of the emporium, 
raises or lowers each price, 
exceptional bargains 
and anti-bargains. 

Even-numbered prices 
divide by two, 
while odd ones climb 
by half themselves 
then half a dollar more 
to keep the numbers whole. 

Today I pause before 
a handsome beveled mirror 
priced at twenty-seven dollars. 
Shall I buy or wait 
for fifty-nine days 
until the price is lower? 

Un incubo del matematico 

Immagina un emporio, 
articoli di valori sconosciuti 
e prezzi arbitrari 
arrotondati per comodità 
a valori interi del dollaro. 

Ogni giorno la Signora X, 
proprietaria dell’emporio, 
alza o abbassa ciascun prezzo: 
occasioni eccezionali 
e anti-occasioni. 

I prezzi con valore pari 
si dividono per due, 
mentre quelli dispari salgono 
della metà del proprio valore 
e poi mezzo dollaro ancora, 
per tenere i numeri interi. 

Oggi mi sono fermata davanti 
a un magnifico specchio molato 
quotato ventisette dollari. 
Lo devo comprare o aspettare 
per cinquantanove giorni 
fino a che il prezzo diventi inferiore? 

Dopo quanti passaggi (giorni) si ottiene un numero più piccolo di 27? Nella versione della congettura fornita da Terras, ciò si verifica esattamente al 59esimo giorno, con il 23. Se la poetessa avesse celebrato la congettura di Collatz nella sua formulazione originale, il cliente avrebbe dovuto aspettare 96 giorni, per soli 4 dollari di risparmio.

4 commenti:

  1. ma è stata già dimostrata? Perché io l'ho dimostrata ma non so dove pubblicare...

    RispondiElimina
  2. se ne parla diffusamente ne "l'ultimo teorema"di Clarke-Pohl. Fantamatematica.

    RispondiElimina
  3. se ne parla diffusamente ne "l'ultimo teorema"di Clarke-Pohl. Fantamatematica.

    RispondiElimina
  4. Purtroppo, la matematica non è ancora pronta per questa roba...

    RispondiElimina