backup del Post

Variazioni sul tema di una successione

Qualche mese fa una mia amica ha postato su Facebook questa successione:

1
11
21
1211
3112
…

Scommetto che parecchi di voi avranno subito detto “che noia, è una successione vecchia come il cucco!”, salvo restare sorpresi dall’ultima riga, che non era proprio quella prevista. Per gli altri, forse è meglio fare un rapido ripasso.

La successione per così dire “classica” ha come primi suoi termini 1, 11, 21, 1211 ma poi continua con 111221, 312211, 13112221 … Avete capito qual è la regola che la produce? È semplice: ogni riga è la riga precedente “pronunciata e contata”. La prima riga è 1, quindi c’è un uno; la seconda sarà così 11, cioè “due uno”; si passa così a 21, vale a dire “un due, un uno”; 1211, “un uno, un due, due uno”; 111221 e così via.

Per quanto stupida possa sembrare la regola di composizione, essa è assolutamente deterministica, e un matematico non trova nulla di strano a studiare la successione, e magari generalizzarla. La prima cosa che salta agli occhi è che una volta che appare un numero questo non può più sparire, visto che sarà sempre pronunciato e quindi contato. Una domanda sorge ora spontanea: ma entreranno man mano a far parte della successione numeri sempre maggiori? La risposta è no: il 3 è il numero maggiore che troverete nella successione. Se volete provare a dimostrarlo da soli, smettete di leggere.

Supponiamo infatti che a un certo punto della successione ci sia un numero al cui interno ci sia una cifra pari o superiore a 4. Questo significa che al passo prima della successione ci devono essere almeno quattro numeri uguali in fila: …nnnn… Ma questo è impossibile, perché o il primo e il terzo, oppure il secondo e quarto dei numeri, saranno identici: ma questo a sua volta significa che al passo precedente la successione non è stata letta correttamente. Non si può infatti avere “due uno, un uno”, perché si sarebbe dovuto scrivere “tre uno”…

Una seconda domanda che ci si può fare vedendo i primi termini della successione è se i vari termini sono sempre più lunghi, e di quanto lo sono. Io non so esattamente come dimostrarlo; però so che John Conway (ho già parlato di lui, ricordate?) ha dimostrato che il rapporto del numero di cifre tra due termini successivi della successione tende a un valore prefissato, detto costante di Conway, noto come λ ~= 1.303577269. Per i curiosoni, questo numero è algebrico, cioè è la soluzione di un’equazione polinomiale a coefficienti interi; per la precisione, è l’unica soluzione positiva della semplice equazione qui sotto (copiata da Wikipedia):

Il disegno qui a fianco, anch’esso tratto da Wikipedia, mostra tutte le radici di quel polinomio. Non serve assolutamente a nulla, anzi serve ancora a meno di tutte le altre cose scritte in questo post, ma aggiunge una punta di allegria… almeno spero.

La costante di Conway non si chiama costante a caso: partendo da una qualunque stringa iniziale – per esempio 42 che ai passi successivi dà 1412, 11141112, 31143112, 132114132112, … – il rapporto della lunghezza di due termini successivi tende ad essa. C’è solo una singola stringa di partenza che è la proverbiale eccezione alla regola. Sapete trovarla?

Convay ha studiato attentamente la successione di cui sopra. Magari una volta o l’altra vi parlerò del decadimento audioattivo; i curiosoni possono scoprire di che si tratta da Roberto Zanasi. Ma torniamo alla nostra successione iniziale: avete riconosciuto la regola che la genera? Anche questa regola non è così difficile: è sempre della serie “leggi e scrivi”, ma si prendono insieme tutti gli elementi uguali. Così da 1211 si ottiene 3112; si inizia da 1 e non da 2 perché il primo elemento trovato partendo da sinistra è un 1. Questa nuova successione dopo 3112 ha 132112, 311322, 232122, 421311… Toh, a differenza del caso classico stavolta siamo riusciti a ottenere un 4. Inoltre è chiaro che la lunghezza dei numeri non aumenta più di tanto, visto che se abbiamo i numeri fino a k al passo successivo avremo un numero di 2k cifre. Arriveremo insomma ad avere numeri sempre maggiori?

La risposta è no. La nostra successione continua con 14123113, 41141223, 24312213, 32142321, 23322114, 32232114, 23322114, 32232114, 23322114, … Oops! sono finito in un loop. Come vedete, questa nuova successione termina in un ciclo di ordine 2, e insomma è molto meno interessante di quella originaria. Non sempre i risultati matematici sono interessanti persino per un Vero Matematico, mi spiace dirlo.

E se provassimo con la successione “leggi e scrivi in ordine”, che inizia con 1, 11, 21, 1112, 3112? In questo caso i termini sono tutti della forma x1y2z3w4…. Beh, i conti si fanno in fretta: si prosegue con 211213, 312213, 212223, 114213, 31121314, 41122314, 31221324, 21322314, 21322314, … Stavolta abbiamo un punto fisso, o se preferite un loop di lunghezza 1; un altro risultato un po’ deludente. Commento? Pensate alla fatica che fa un matematico per trovare qualcosa di divertente – almeno dal suo punto di vista –. La stessa cosa, se vi ricordate, capitò con il problema 3n+1; cambiare la formula non dava i risultati sperati. Lo stesso capita con un’altra creazione di Conway, Life: la scelta delle regole di evoluzione non è stata fatta a caso, ma ha richiesto un attento lavoro. Anche la creazione di giochi matematici è per l’un percento ispirazione e per il 99% traspirazione: attenti alle vostre ascelle!