Fibonacci amagat dins de Collatz

Com la successió més famosa de les matemàtiques va aparèixer, sense que ningú la convidés, dins del problema que ningú sap resoldre.

Aquesta història ajunta dos personatges que, en principi, no tenen res a veure. Un és una celebritat: els nombres de Fibonacci, aquella successió que surt als llibres de divulgació, als gira-sols i fins i tot a El codi Da Vinci. L'altre és un problema amb una fama curiosa: la conjectura de Collatz, una pregunta d'enunciat infantil que fascina els aficionats, incomoda els matemàtics professionals i porta des de 1937 sense resposta.

El que t'explicaré aquí és un resultat de la meva tesi doctoral: un teorema que demostra que, dins de la dinàmica de Collatz, els nombres de Fibonacci estan comptant una cosa molt concreta. No és una coincidència numèrica ni una curiositat aproximada: és una igualtat exacta, vàlida per sempre, amb demostració. I el millor és que el camí complet —des de la definició de Fibonacci fins al teorema— es pot recórrer amb matemàtiques de batxillerat. Recorrem-lo.

1. Els nombres de Fibonacci

La regla és la més simple imaginable: comença amb \(1, 1\) i, a partir d'aquí, cada terme és la suma dels dos anteriors.

\[ F(1)=1,\quad F(2)=1,\quad F(n)=F(n-1)+F(n-2). \]

Fixa't en el quocient entre termes consecutius que mostra el simulador. A mesura que avances, s'acosta a un nombre molt concret:

\[ \varphi=\frac{1+\sqrt5}{2}=1{,}6180339\ldots \]

És el famós nombre auri. No és casualitat: els nombres de Fibonacci creixen, a la llarga, multiplicant-se per \(\varphi\) a cada pas. Guarda't aquesta dada, perquè \(\varphi\) reapareixerà al final de la història al lloc més inesperat.

On viuen de debò (i on no)

Segur que has sentit que la closca del nautilus és una «espiral àuria». Em sap greu esguerrar-ho: no ho és. És una espiral logarítmica, sí, però amb una altra proporció; això de Fibonacci aquí és un mite que es repeteix de llibre en llibre. En canvi, hi ha llocs on els nombres de Fibonacci apareixen de debò i per raons que s'entenen: les espirals de les llavors d'un gira-sol o les escames d'una pinya solen venir en parelles de nombres de Fibonacci consecutius (8 i 13, 21 i 34), perquè aquesta disposició és la manera més eficient d'empaquetar llavors que van naixent girades un angle fix.

Però l'hàbitat natural de Fibonacci no és la botànica: és el recompte de camins. L'exemple clàssic: de quantes maneres pots pujar una escala de \(n\) graons si a cada pas puges 1 o 2?

El perquè cap en una frase: per arribar al graó \(n\), el teu últim pas va ser d'1 (venies del \(n-1\)) o de 2 (venies del \(n-2\)); per tant, maneres d'arribar a \(n\) = maneres d'arribar a \(n-1\) + maneres d'arribar a \(n-2\). Aquesta és exactament la regla de Fibonacci. Quan un problema es redueix a comptar camins amb dues opcions que s'encadenen així, Fibonacci apareix sol. Recorda aquesta idea: és la clau de tot el que ve.

2. La conjectura de Collatz

Agafa qualsevol nombre enter positiu. Si és parell, divideix-lo entre 2. Si és senar, multiplica'l per 3 i suma-li 1. Repeteix. La conjectura de Collatz afirma que, comencis on comencis, sempre acabes arribant a l'1. Gairebé noranta anys després, ningú ha pogut demostrar-ho ni trobar un contraexemple — i no és per manca d'evidència: s'ha comprovat amb ordinador, un a un, per a tots els nombres fins a \(2^{71}\) (més de dos mil trilions). Que es compleixi dos mil trilions de vegades seguides no demostra que es compleixi sempre: aquesta distància entre comprovar i demostrar és el cor del problema.

Els matemàtics solem fer servir una versió «accelerada» de la regla. Com que \(3n+1\) sempre és parell quan \(n\) és senar, podem dividir entre 2 immediatament i estalviar-nos un pas:

\[ T(n)=\begin{cases} n/2 & \text{si } n \text{ és parell},\\[2pt] \dfrac{3n+1}{2} & \text{si } n \text{ és senar}. \end{cases} \]

Amb aquesta versió, el final del viatge és el petit cicle \(1\to2\to1\). Tot el que segueix fa servir \(T\).

Prova amb 27: puja fins a prop de 5.000 abans de rendir-se. Prova amb 26: hi arriba de seguida. Veïns de porta, destins oposats. Aquest és el caràcter del problema: la regla és trivial, però el comportament és salvatge i imprevisible.

I tanmateix, hi ha una manera de domar aquest caos. Consisteix a canviar de lent: deixar de mirar el nombre i mirar una altra cosa molt més humil.

Aquesta altra cosa és el residu en dividir entre 6: el nombre entre 0 i 5 que sobra. El 27 deixa residu 3 (perquè \(27 = 4\cdot 6 + 3\)); el 80 deixa residu 2; i per enorme que sigui el nombre, el seu residu és sempre un d'aquests sis valors. Res més.

Aquí hi ha el canvi decisiu, i val la pena aturar-s'hi. Els nombres viuen en un espai infinit: salten a milers, sense manera de preveure on aniran. Però els seus residus viuen en un espai diminut — només sis valors possibles, passi el que passi. Així que mentre la trajectòria d'un nombre es dispara sense patró aparent, la trajectòria dels seus residus està obligada a moure's entre sis caselles. I el millor: no salta entre elles per caprici, sinó seguint regles fixes. És com canviar un mapa infinit i sense camins per un tauler de sis caselles amb les fletxes ja marcades.

Vegem-ho. Llancem un altre cop una trajectòria —la mateixa d'abans, si vols— però aquest cop acolorint cada nombre segons el residu que deixa en dividir-lo entre 6:

Això és el que cal veure: per molt lluny que voli la trajectòria, els colors només ballen entre sis. Aquest petit ball, finit i reglat, és el que estudiarem — i és on, al final, apareixerà Fibonacci.

3. Un mapa amb sis regions

Posem nom a les sis caselles: les anomenarem «regions», una per cada residu (0 a 5). La pregunta, l'única que cal, és: si un nombre és a la regió \(r\), a quina regió el pot enviar \(T\)?

I es respon amb pura aritmètica d'institut. Prenguem la regió 1. Un nombre amb residu 1 s'escriu \(n=6k+1\) per a algun enter \(k\ge 0\); com que és senar, \(T\) l'envia a:

\[ T(n)=\frac{3n+1}{2}=\frac{3(6k+1)+1}{2}=9k+2. \]

I quin residu deixa \(9k+2\) en dividir entre 6? Aquí hi ha la idea, i és l'única cosa que cal entendre: el resultat canvia segons que \(k\) sigui parell o senar. I la raó cap en una ratlla: com que \(9k+2 = 6k + (3k+2)\), el residu el decideix \(3k\), que val 0 si \(k\) és parell i 3 si és senar. Així que \(9k+2\) deixa residu 2 quan \(k\) és parell, i residu 5 quan és senar. Per tant la regió 1 té dues sortides — a la 2 i a la 5 —, una per cada paritat de \(k\). Aquestes són les dues fletxes que surten de la regió 1 al mapa, i per això van en dos colors: verd per a \(k\) parell, ambre per a \(k\) senar.

Amb les altres cinc regions es fa igual (si \(n\) és parell, surt \(n/2\), encara més senzill). El resultat són dotze fletxes, dues per regió — aquest mapa. Prem qualsevol regió per veure'n el càlcul i encendre les seves dues fletxes:

Aquest mapa té dos trets que val la pena mirar de prop, perquè d'ells surt tota la resta.

Les regions 0 i 3 només tenen fletxes de sortida. Són regions diferents —la 0 són els múltiples de 6 i la 3 són els múltiples de 3 senars—, però juntes formen els múltiples de 3, i comparteixen una peculiaritat: cap fletxa del nucli no hi arriba. La raó és senzilla. Per caure en un múltiple de 3 caldria partir ja d'un: si \(n\) és senar, \(\tfrac{3n+1}{2}\) mai és múltiple de 3 (perquè \(3n+1\) no ho és); i si \(n\) és parell, \(n/2\) només és múltiple de 3 quan \(n\) ja ho era. Així que es pot començar en un múltiple de 3, però un cop se'n surt, no s'hi torna mai més.

Les altres quatre regions \(\{1,2,4,5\}\) formen el nucli del sistema. Tota trajectòria acaba a dins —pel que acabem de veure: tard o d'hora s'abandona el club dels múltiples de 3 i no s'hi torna mai— i, un cop a dins, es circula entre elles per sempre. Cada regió del nucli té exactament dues sortides: des de l'1 es va a 2 o a 5; des del 2, a 1 o a 4; des del 4, a 2 o a 5; des del 5, a 2 o a 5. Dos camins possibles a cada pas vol dir que el nombre de trajectòries es duplica a cada pas: 2, 4, 8, 16… Creix de pressa, però de manera perfectament regular. Queda't amb aquesta paraula —duplica—, perquè a la propera secció traurem del mapa una sola regió i veurem com aquest «duplica» es transforma, sense avisar, en una cosa molt més interessant.

4. La regió prohibida: el subgraf \(H_4\)

Ara ve la pregunta que ho desencadena tot. De les quatre regions del nucli, la regió 4 és especial: només s'hi arriba des d'una, la regió 2 (comprova-ho a l'explorador d'abans: és l'única fletxa que apunta al 4). I si un nombre se les enginya per esquivar-la sempre? Quants n'hi ha capaços de circular pel nucli sense trepitjar mai la regió 4?

Per respondre-la, traiem del mapa la regió 4 i ens quedem només amb \(\{1,2,5\}\) i les fletxes entre elles. (Un pont de vocabulari, perquè d'ara endavant és còmode: el que anem anomenant «mapa» és en realitat un graf, i cada regió és un vèrtex seu; en treure una regió ens queda un subgraf. A aquest l'anomeno \(H_4\): el que sobreviu en esborrar la regió 4.)

Observa què ha passat en esborrar el 4: les regions 1 i 5 conserven les seves dues sortides, però la regió 2 n'ha perdut una —la seva fletxa cap al 4— i es queda amb una de sola: tornar a 1. El nucli complet oferia sempre dues opcions per pas; \(H_4\) ofereix dues opcions, llevat que trepitgis el 2, que només en ofereix una. Aquesta petita asimetria —dos camins gairebé sempre, un de sol en trepitjar el 2— és la que fabricarà Fibonacci. Vegem-ho.

La matriu que compta camins

Aquí hi ha l'única idea d'àlgebra que ens cal, i val la pena entendre-la, no només creure-se-la. Comencem pel més fàcil. La mateixa matriu \(M\) ja compta els camins d'un pas: la seva casella \((r,s)\) val 1 quan hi ha una fletxa de \(r\) a \(s\) —un camí de longitud 1— i 0 quan no n'hi ha.

I els camins de dos passos? Per anar de \(r\) a \(s\) en dos passos cal aturar-se en alguna regió intermèdia \(t\): primer \(r\to t\), després \(t\to s\). Comptar de quantes maneres es pot fer és justament el que fa multiplicar la matriu per ella mateixa: la casella \((r,s)\) de \(M^2\) recorre totes les regions intermèdies \(t\) possibles i suma «hi ha fletxa \(r\to t\)?» per «hi ha fletxa \(t\to s\)?». Encadenant el mateix pas a pas s'arriba a la regla general:

I no cal creure-s'ho: a la taula de baix, prem qualsevol casella i veuràs aquests camins escrits un a un.

Apuja el lliscador a poc a poc i mira les entrades de la matriu: 1, 1, 2, 3, 5, 8, 13, 21… Totes i cadascuna de les entrades de \(M^k\) són nombres de Fibonacci, i els totals de camins per fila també. No els hi hem posat nosaltres: els ha fabricat el graf.

I per què Fibonacci, i no una altra successió qualsevol? El bonic és que es pot veure sense ni un sol càlcul, mirant només el mapa de \(H_4\). Comptem els camins de longitud \(k\) que arrenquen a la regió 1 —els mateixos que compta el simulador— i anomenem-los \(C(k)\). El primer pas només pot anar a 2 o a 5:

Si va a 5, passa una cosa afortunada: la regió 5 té exactament les mateixes sortides que la 1 (a la matriu, les seves dues files són idèntiques). Així que seguir des de 5 és com tornar a començar el recompte des de l'1: queden \(C(k-1)\) camins. Si va a 2, la regió 2 no pot triar —la seva única sortida és tornar a 1—, així que el camí gasta dos passos (\(1\to2\to1\)) i torna al punt de partida: queden \(C(k-2)\) camins. Sumant les dues possibilitats:

\[ C(k) = C(k-1) + C(k-2). \]

És, lletra per lletra, la regla de Fibonacci. I ara sí que és exactament la de l'escala: dues maneres de continuar, una que avança un pas (anar a 5) i una altra que «salta» dos (la marrada \(1\to2\to1\)). L'asimetria del 2 no era un detall: era el motor.

Fixa't en el que aquesta recurrència significa per al ritme de creixement. A la secció 1 vam veure que els nombres de Fibonacci creixen, a la llarga, multiplicant-se per \(\varphi\) a cada pas. Com que els nostres camins obeeixen exactament la mateixa regla, creixen al mateix ritme: el nombre de camins per \(H_4\) es multiplica per \(\varphi=1{,}618\ldots\) —ja t'havia dit que el nombre auri reapareixeria—. En canvi, al nucli complet, on cada regió sí que té dues sortides de debò, el nombre de camins es duplica: es multiplica per 2. Dos ritmes diferents, \(\varphi\) contra 2 (els matemàtics anomenen aquest ritme el radi espectral del graf), i aquesta diferència ho canvia tot:

Mira com se separen les dues barres: com més gran és \(m\), més rar és esquivar la regió 4 — els camins que l'eviten són una fracció del total que s'encongeix sense fre, al ritme \((\varphi/2)^m\). I ara, per fi, recupera la pregunta del principi. Pel diccionari nombre↔camí de la secció anterior, els nombres que esquiven la regió 4 són exactament aquests camins de \(H_4\). Així que ja tenim la resposta completa: quants nombres esquiven el 4 ho diuen els nombres de Fibonacci, i què rars es tornen ho diu el quocient \(\varphi/2\). Això, posat en net, és el teorema.

5. El teorema

Ajuntem les peces. Els nombres que eviten la regió 4 són, via el graf, camins a \(H_4\); els camins a \(H_4\) els compten les potències de \(M\); i les potències de \(M\) fabriquen nombres de Fibonacci. Però l'enunciat exacte afina dues coses que semblen detalls i són justament on hi ha la subtilesa: parla de nombres senars i comença a mirar des del segon pas. Val la pena entendre per què.

Primer, fixem les paraules, perquè aquí és fàcil embolicar-se. L'òrbita d'un nombre \(n\) és la successió que surt d'aplicar \(T\) una vegada i una altra: \(n,\ T(n),\ T(T(n)),\ \ldots\) Anomenarem pas 1 el mateix \(n\), pas 2 \(T(n)\), pas 3 \(T(T(n))\), i així: el pas \(k\) és el resultat d'aplicar \(T\) un total de \(k-1\) vegades. (Farem servir sempre «pas» per a aquesta posició i «aplicar \(T\)» per a l'operació; convé no barrejar les dues paraules.)

I ara el fet que ho explica tot, i que pots comprovar: agafis el nombre senar que agafis, una sola aplicació de \(T\) el deixa a la regió 2 o a la 5 — és a dir, dins de \(H_4\). Mira-ho: \(7\to11\equiv5\), \(9\to14\equiv2\), \(15\to23\equiv5\). Tant és que el senar de partida sigui un múltiple de 3 —com 3, 9 o 15, que viuen a la regió 3, fora del nucli—: al primer pas hi aterra igualment, i net, dins de \(H_4\).

D'aquí surten les dues condicions. Es compten senars perquè la seva entrada a \(H_4\) és sempre neta i d'un sol pas; els parells es porten pitjor —un múltiple de 6 pot quedar-se voltant a la regió 0, que té una fletxa cap a si mateixa, durant uns quants passos abans d'entrar al nucli (per exemple \(24\to12\to6\to3\), tres passos a la regió 0)—. I es mira des del pas 2 perquè el pas 1 és el senar de partida: el seu residu mai és 4 (és senar), de manera que demanar-li que «eviti la regió 4» no diria res, i a més podria ser un múltiple de 3, que ni tan sols és encara al nucli. És a partir del pas 2 que tot senar està garantit dins de \(H_4\), i la pregunta «aconsegueix quedar-s'hi, esquivant la regió 4?» es converteix exactament en el nostre recompte de camins. La seva resposta és un enunciat exacte:

Ni «aproximadament», ni «per a \(m\) gran»: exactament el nombre de Fibonacci \(F(m+1)\), per a tot \(m\). Per exemple, amb \(m=6\): dels 32 nombres senars fins a 64, exactament 13 \(=F(7)\) esquiven la regió 4. I el ritme \((\varphi/2)^m\)? És justament el duel \(\varphi\) contra 2 del visor anterior: els supervivents creixen com \(\varphi\) i el total com 2, així que la seva proporció s'apaga sola. Esquivar la regió 4 és possible, però cada cop més rar; gairebé tots els nombres acaben trepitjant-la.

No te'n refiïs, de mi — comprova-ho. Aquest verificador executa el càlcul de debò, nombre a nombre; i pots prémer qualsevol nombre per obrir-ne l'òrbita i veure com esquiva —o no— la regió 4:

6. Per què importa

Una connexió entre Fibonacci i Collatz ja és bonica per si sola, i no és la primera vegada que algú l'entreveu: a «Collatz Meets Fibonacci» (Albert, Gudmundsson i Ulfarsson, 2022), certs recomptes lligats a Collatz coincideixen amb els nombres de Fibonacci… fins a longitud 14, i a partir d'aquí la coincidència es trenca i apareixen termes «de més». La diferència aquí és que el recompte és exacte —\(F(m+1)\), per a tot \(m\) sense excepció— i amb demostració tancada. Però el teorema diu, a més, una cosa més profunda sobre l'estructura del problema.

Al paper es demostra que cap vèrtex del nucli no és prescindible: esborris el que esborris, la velocitat de creixement cau estrictament per sota de 2, i cada vèrtex té el seu preu exacte. Esborrar el 4 (o l'1) la deixa en \(\varphi\approx1{,}618\); esborrar el 5, en \(\sqrt2\approx1{,}414\); i esborrar el 2 l'enfonsa fins a 1: sense la regió 2, amb prou feines queda un fil de camins. La jerarquia completa, \(1<\sqrt2<\varphi<2\), mesura quant sosté cada regió el trànsit de la dinàmica.

I això té una conseqüència directa sobre la conjectura. Si existís un cicle diferent del \(1\to2\to1\) —una de les dues maneres en què Collatz podria ser falsa—, aquest cicle seria un camí tancat al graf, i un camí tancat ha de quadrar amb les regles de trànsit del mapa: a cada regió, les vegades que s'hi entra i les vegades que se'n surt s'han de compensar. D'aquesta comptabilitat surt una cosa molt concreta: el teorema obliga que tot cicle positiu de \(T\) ha de visitar la regió 2, i a més passar-hi més del 18% dels seus passos. No sabem si aquests cicles existeixen, però ja sabem una cosa concreta sobre com haurien de ser: no hi ha cap cicle possible que visqui amagat als marges del mapa.

Aquesta és, per a mi, la moralitat de tot plegat. La conjectura de Collatz continua oberta, i aquest teorema no la resol. Però demostra que sota el caos aparent de les trajectòries hi ha una estructura rígida, mesurable i exacta — tan exacta que al seu cor bateguen, des de sempre i sense que ningú els hagués vist, els nombres de Fibonacci i el nombre auri.

---