Dalle relazioni di ricorrenza alla simmetria dei palindromi. Come la base 2 trasforma un enigma matematico in un gioco combinatorio.
L’esercizio che segue fu proposto alle Olimpiadi Internazionali di Matematica (IMO) che si svolsero a Canberra (Australia) dal 9 al 21 luglio 1988. La questione che pone nasconde nelle pieghe del suo formalismo un legame inatteso.
Sia \(f\) una funzione definita sugli interi positivi da
\[
f(1)=1,\qquad f(3)=3,
\]
e, per ogni \(n\ge1\),
\[
f(2n)=f(n),
\]
\[
f(4n+1)=2f(2n+1)-f(n),
\]
\[
f(4n+3)=3f(2n+1)-2f(n).
\]
Si chiede di determinare quanti interi positivi \(n\le1988\) soddisfano l'equazione \(f(n)=n\).
Per capire qualcosa del comportamento della funzione conviene, con po' di pazienza, calcolare almeno i primi valori:
\[
\begin{array}{c|ccccccccccccccc}
n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\
\hline
f(n)&1&1&3&1&5&3&7&1&9&5&11&3&13&7&15
\end{array}
\]
Ecco allora una prima indicazione: la relazione \(f(2n)=f(n)\) mostra che la funzione "ignora" completamente i fattori pari; se scriviamo \(n=2^k m\) con \(m\) dispari, si ha sempre \(f(n)=f(m)\). Di conseguenza, il comportamento della funzione è interamente determinato dai suoi valori sui numeri dispari.
Altre indicazioni però provengono dalle altre due relazioni:
\[
f(4n+1)=2f(2n+1)-f(n),
\]
\[
f(4n+3)=3f(2n+1)-2f(n).
\]
Esse distinguono i numeri della forma \(4n+1\) e \(4n+3\). Questi sono precisamente i numeri dispari che in base 2 terminano rispettivamente con le cifre \(01\) e \(11\). La struttura stessa della ricorrenza sembra quindi suggerire che la rappresentazione binaria giochi un ruolo essenziale.
Per verificare questa intuizione, isoliamo i valori della funzione sui primi numeri dispari ed esprimiamo sia l'argomento sia il risultato in base 2:
\[
\begin{array}{c|c|c}
m & \text{m in base 2} & \text{f(m) in base 2}\\
\hline
1 & 1 & 1\\
3 & 11 & 11\\
5 & 101 & 101\\
7 & 111 & 111\\
9 & 1001 & 1001\\
11 & 1011 & 1101\\
13 & 1101 & 1011\\
15 & 1111 & 1111
\end{array}
\]
Ora emerge una sorprendente regolarità. Nei casi mostrati, la rappresentazione binaria di \(f(m)\) si ottiene leggendo quella di \(m\) da destra verso sinistra. Ad esempio, \(11=(1011)_2\) viene trasformato in \((1101)_2=13\), mentre \(13=(1101)_2\) viene trasformato in \((1011)_2=11\). Sembra dunque che la funzione operi una sorta di riflessione speculare sulle cifre binarie.
Naturalmente alcuni esempi non costituiscono una dimostrazione. Occorre verificare che questa regola sia realmente compatibile con le relazioni ricorsive.
La congettura e la dimostrazione
Indichiamo con \(R(m)\) il numero ottenuto invertendo l'ordine delle cifre della rappresentazione binaria di un numero dispari \(m\). La congettura suggerita dagli esempi è quindi: \(f(m)=R(m)\).
Dimostriamola per induzione sulla lunghezza della rappresentazione binaria. I casi iniziali \(m=1\) e \(m=3\) coincidono con la definizione della funzione. Supponiamo ora che la proprietà sia vera per tutti i numeri dispari con meno cifre binarie di \(m\).
Ogni numero dispari maggiore di \(1\) termina necessariamente con una cifra \(1\) e può essere scritto in uno dei due modi: \(m=4n+1\) oppure \(m=4n+3\). In termini binari, queste due forme corrispondono all'aggiunta finale delle coppie di cifre \(01\) oppure \(11\).
Le due relazioni ricorsive mostrano allora che il valore di \(f(m)\) si ottiene esattamente trasferendo quella cifra finale all'inizio della rappresentazione binaria del risultato, cioè invertendo progressivamente l'ordine delle cifre. L'ipotesi induttiva garantisce che tale procedimento coincide con la lettura speculare dell'intera rappresentazione binaria. Pertanto, \(f(m)=R(m)\) per ogni numero dispari \(m\).
Poiché inoltre \(f(2^k m)=f(m)\), possiamo enunciare il comportamento della funzione in modo particolarmente semplice:
La funzione elimina tutti i fattori 2 e poi legge al contrario la rappresentazione binaria della parte dispari del numero.
I punti fissi
A questo punto siamo pronti per risolvere l'equazione \(f(n)=n\).
Se \(n\) fosse pari (\(n=2^k m\) con \(k>0\)), si avrebbe \(f(n)=f(m)\), che è un numero dispari. Di conseguenza, un numero pari non può mai essere un punto fisso. Ogni soluzione deve quindi essere un numero dispari.
Per i numeri dispari la condizione \(f(m)=m\) si traduce in \(R(m)=m\). Questo significa che la rappresentazione binaria del numero deve coincidere con la sua inversione:
I punti fissi di \(f\) sono esattamente i numeri palindromi in base 2.
I primi due punti fissi sono immediati dalla definizione: \(1\) (in binario \(1\)) e \(3\) (in binario \(11\)). Se cerchiamo i successivi palindromi binari a 3 cifre, questi devono iniziare e terminare con \(1\), assumendo la forma \(1\ \_\ 1\). Abbiamo due possibilità per la cifra centrale:
- \((101)_2=5\)
- \((111)_2=7\)
I primi punti fissi della funzione in ordine crescenti sono dunque: \(1,3,5,7,\ldots\)
Quanti fino a 1988
Poiché \(1988 < 2^{11}=2048\), i numeri cercati hanno al più 11 cifre in base 2.
Un palindromo binario di lunghezza \(k\) è completamente determinato dalla sua prima metà (poiché la prima cifra deve essere sempre \(1\)). Il numero di palindromi di lunghezza \(k\) è quindi \(2^{\lceil k/2\rceil-1}\).
Sommando i palindromi per le lunghezze da 1 a 10 si ottiene:
\[
1+1+2+2+4+4+8+8+16+16=62.
\]
Restano da contare i palindromi di 11 cifre minori o uguali a 1988. Poiché \(1988 = (11111000100)_2\), un palindromo di 11 cifre è completamente determinato dalle sue prime 6 cifre.
Le stringhe di 6 cifre comprese tra \(100000\) e \(111101\) sono esattamente 30 e generano tutte palindromi inferiori a 1988. La stringa successiva, \(111110\), genera invece il palindromo \((11111011111)_2=2015\), che supera il limite assegnato. Pertanto i palindromi validi di 11 cifre sono esattamente 30.
Il numero totale dei punti fissi fino a 1988 è dunque:
\[
62+30 = \boxed{92}.
\]
Una variante didattica: il conteggio fino al 2026
Se desideriamo attualizzare l'esercizio per proporlo in una gara scolastica o in un compito in classe, possiamo sostituire la soglia storica del 1988 con l'anno corrente, il 2026.
Poiché anche \(2026 < 2^{11}=2048\), la prima parte del conteggio non cambia: i palindromi binari da 1 a 10 cifre sono sempre 62. Esprimendo il nuovo limite in base 2 si ha:
\[
2026=(11111101010)_2.
\]
In questo caso, le 31 stringhe iniziali comprese tra \(100000\) e \(111110\) generano tutte palindromi minori di 2026. La stringa massima \(111111\) produce invece il palindromo \((11111111111)_2=2047\), che supera il limite. I palindromi validi di 11 cifre sono quindi 31 e il numero totale dei punti fissi diventa:
\[
62+31 = \boxed{93}.
\]
Conclusione
Un problema apparentemente enigmatico si risolve rivelando un'elegante struttura nascosta. Le relazioni ricorsive conducono naturalmente alla rappresentazione binaria, la rappresentazione binaria conduce all'idea di inversione, e l'inversione conduce ai palindromi. Così un quesito che inizialmente appare oscuro si trasforma in un buon esercizio di conteggio combinatorio.
COMMENTS