The Magic Zeckendorf World

In questo post si indaga su alcune questioni di combinatoria. I primi due spunti sono tratti da altrettanti problemi presenti nel test di ammissione al primo anno SNS, annata 2010.

Genesi di un sostenibile vincolo. In principio vi era B, l’insieme delle stringhe binarie, sequenze di lettere appartenenti ad un alfabeto con soli due simboli, 0 ed 1. Successivamente venne V, insieme delle stringhe binarie “vincolate”, dove non figurano due 0 consecutivi. Denotando con |s| la lunghezza di una stringa s, Dio si chiese se esistesse una mappa biunivoca f:B->V con la proprietà addizionale che per ogni stringa s sufficientemente lunga, |f(s)|/|s| < 3/2.

Ogni elemento di V è concatenazione di un 1 con un elemento di V, o della stringa 01 con un elemento di V. Ne segue che, se denotiamo con V_n il numero di stringhe in V di lunghezza n, si ha:
V₁=2,       V₂=3,      V_n+2 = V_n+1+V_n,
ed è evidente il nesso con i numeri di Fibonacci. Detti U^* e V^* gli insiemi U e V lessicograficamente ordinati, una possibile divina mappa biunivoca è quella che associa il k-esimo elemento di U^* al k-esimo elemento di V^*, ed è intuitivo che meglio di così c’è poco. Limitiamo dunque il “rapporto di espansione” di questa mappa f, ossia chiediamoci quale sia l’indice del più piccolo elemento di U^* la cui codifica tramite f annoveri esattamente m caratteri. Quest’indice sarà:
V₁ + V₂ + … + V_m-1 + 1 = V_m+1 – 2,
e il corrispondente elemento s di U^* sarà costituito da almeno
log₂(V_m+1)-1
caratteri, da cui:
|f(s)|/|s| <= m/(log₂(V_m+1)-1).
Facendo ora ricorso alla formula di Binet, è relativamente semplice verificare che il rapporto di espansione della nostra mappa è definitivamente inferiore a 13/9 < 3/2.

Una soluzione più elegante (nonché computazionalmente più efficiente) passa attraverso il teorema di Zeckendorf: ogni numero naturale ammette un’unica rappresentazione come somma di numeri di Fibonacci con indici non consecutivi; chiamiamo allora tale rappresentazione “codifica di Zeckendorf”. Possiamo costruire una biezione tra U e V nel seguente modo: dato un elemento s di U, ne calcoliamo l’indice i in U^*, guardiamo gli indici coinvolti nella codifica di Zeckendorf di i e restituiamo una stringa che abbia 0 in tali posizioni. Per le proprietà della codifica di Zeckendorf, tale stringa appartiene a V. Per quanto concerne la mappa inversa, dato v in V, chiamiamo i la somma dei numeri di Fibonacci aventi come indici gli indici degli 0 in v, dunque restituiamo l’i-esimo elemento di U^*. Lasciamo al lettore l’ingrato compito di verificare che tale mappa è analoga alla “corrispondenza lessicografica” tra U^* e V^* già analizzata.

Genesi di un insetto di Markov. Al termine dell’estate nacque una pulce isterica, che si muoveva sui vertici di un pentagono, scegliendo, ogni secondo, se saltare verso destra o verso sinistra, con pari probabilità. Dio si chiese se dopo 28 secondi la probabilità di aver visitato ogni vertice fosse maggiore di 1/2. O se, addirittura, bastassero 22 secondi.

E’ evidente la corrispondenza biunivoca tra i percorsi intrapresi dalla pulce e le stringhe binarie, come pure il fatto che, se una stringa contiene quattro 0 o quattro 1 consecutivi, il percorso associato visita almeno una volta tutti e 5 i vertici del pentagono. Stimiamo allora il numero di stringhe binarie di 28 caratteri che NON presentino né quattro 0 né quattro 1 consecutivi: dividendo una siffatta stringa in 7 blocchi adiacenti di lunghezza 4, nessuno dei blocchi può coincidere con la stringa 0000 o con la stringa 1111, dunque vi sono al più
(14/16)⁷ * 2²⁸ = (7/8)⁷ * 2²⁸
percorsi di lunghezza 28 che NON visitano ogni vertice. Tuttavia
(7/8)⁷ < 1/2,
in quanto tale disuguaglianza è equivalente a
8⁷ > 2 * 7⁷,
che è una semplice conseguenza della disuguaglianza di Bernoulli:
8⁷ = (7+1)⁷ = 7⁷ + 7*7⁶ + … > 2 * 7⁷,
abbiamo dunque provato il divino claim per i percorsi di lunghezza 28, ma per quelli di lunghezza 22 occorrerà una maggiore accuratezza: proviamo a stimare il numero di stringhe binarie di 22 caratteri che NON presentano quattro 0 o quattro 1 consecutivi, senza ripartirle barbaramente in sotto-blocchi. Denotiamo con V l’insieme delle stringhe binarie che NON contengono quattro zeri consecutivi e con V_n il numero di elementi di V di lunghezza n. Si ha:
V₁=2,     V₂=4,    V₃=8,    V₄=14,
V_n+4 = V_n+3 + V_n+2 + V_n+1 + V_n,
in quanto i gli unici possibili prefissi per un elemento di V sono 1, 01, 001, 0001.
Detto p(x) il polinomio caratteristico della ricorrenza appena determinata,
p(x)=x⁴-x³-x²-x-1,  con zeri z_j,  si ha:
V_n = k₁ z₁ⁿ + k₂ z₂ⁿ + k₃ z₃ⁿ + k₄ z₄ⁿ
per un certo set di costanti k_j, in perfetta analogia con la formula di Binet per i numeri di Fibonacci. L’insieme delle sequenze con polinomio caratteristico p(x) determina uno spazio vettoriale di dimensione 4; sia ora M la matrice compagna di p(x) e T_m la traccia di M^m: la sequenza T appartiene a tale spazio vettoriale in virtù del teorema di Cayley-Hamilton; si ha:
T_k=z₁^k+z₂^k+z₃^k+z₄^k,
T₁=1,   T₂=3,   T₃=7,   T₄=15.
E’ semplice provare, per induzione, che per ogni n maggiore di 4 si ha
V_n < T_n+T_n-3,
in quanto la differenza tra il membro destro e il membro sinistro è una sequenza avente p(x) come polinomio caratteristico. Cerchiamo ora di localizzare con buona precisione gli zeri di p(x). Si ha:
p(x)(x-1) = x^4 (x – 2) + 1.
Per il teorema di Rouché, p(x) ha tre zeri di modulo inferiore ad 1. Di questi, uno solo è reale ed è compreso tra -4/5 e -3/4. L’ulteriore zero, che battezziamo “radice dominante”, è reale ed appena minore di 2: applicando due volte il metodo di Newton al polinomio p(x)(x-1) è relativamente semplice verificare che la radice dominante è più piccola di (2-1/14). Per quanto asserito in precedenza si ha allora:
V_n < (8/7) (2-1/14)ⁿ.
Sia ora D_n il numero di stringhe binarie di lunghezza n dove appaiono SIA quattro 0 che quattro 1 consecutivi. Una maggiorazione piuttosto brutale per D_n è la seguente:
D_n < 2^n-6.
Se ora denotiamo con U_n il numero di stringhe binarie di lunghezza n dove appaiono quattro zeri consecutivi O quattro 1 consecutivi abbiamo:
2^-n U_n > (2-1/64) – (16/7) (1-1/28)ⁿ.

Genesi di oggetti mirabolanti. Infine Dio si iscrisse ad un forum di matematica frequentato da loschi figuri, e si imbattè in un mostro: http://www.scienzematematiche.it/forum/viewtopic.php?f=7&t=2190.

Diverse questioni nascono da qui: in primis, il teorema di Zeckendorf. In secondo luogo, il teorema di Beatty, per cui ogni numero naturale positivo n, per un qualche m, è parte di intera di m volte il rapporto aureo o di m volte il quadrato del rapporto aureo. Detta sequenza di Wythoff la successione dei naturali per cui vale la prima, si ha una caratterizzazione alternativa. La sequenza di Wythoff, infatti, è costituita da tutti e soli i naturali positivi per cui l’indice del più piccolo numero di Fibonacci che appare nella codifica di Zeckendorf è pari (qui si sta assumendo F₀=1, F₁=2). Verrebbe dunque da chiedersi se valgano generalizzazioni del teorema di Zeckendorf per i Tribonacci o i Tetranacci numbers, ossia per le sequenze aventi polinomi caratteristici x³-x²-x-1 e x⁴-x³-x²-x-1, e quali caratteristiche abbia la partizione dei naturali indotta dalla classe di resto (modulo 3, o modulo 4) del più piccolo *-acci number che appaia nella codifica di Zeckendorf generalizzata.

E’ naturale anche chiedersi quante siano le stringhe binarie di m caratteri che non contengano k caratteri consecutivi uguali: il problema ammette una soluzione relativamente semplice in termini di matrici di transizione associate a un grafo, e prodotti di Kronecker; quel che si verifica è che il polinomio caratteristico della ricorrenza non è libero da quadrati, dunque il comportamente asintotico della quantità cercata è analogo a quello di mα^m, per un’opportuna costante α, radice del polinomio caratteristico compresa tra 1 e 2.

In quest’ottica, sapreste stimare il numero di percorsi suriettivi della pulce del secondo problema?