Il problema

Note: questo articolo fa uso di MathML, lo standard XML per le formule matematiche. Purtroppo, questo non è supportato correttamente in alcuni browser sedicenti ‘moderni’ o ‘ricchi di funzionalità’. Se le formule non hanno senso nel tuo browser, segnala il problema agli sviluppatori (del browser), o passa ad un browser che supporti questi standard.

Si pone il seguente problema, derivato da questo articolo su G+: determinare la formula esplicita della successione di numeri naturali1 (ovvero della funzione F:) che soddisfa le due seguenti condizioni:

  1. è strettamente crescente;
  2. l'i-esimo elemento non appartenente all'immagine di F è F(F(i))+1.

Vediamo innanzi tutto di capire bene il secondo punto, cominciando con l'osservare che l'unica successione strettamente crescente che ha come immagine l'intero è la successione a(n)=n. Per dimostrarlo, prendiamo una qualunque (altra) successione strettamente crescente b e sia k il primo indice per cui b(k)k; risulterà anzi necessariamente2 b(k)>k, ed avremo quini b(n)=n<kn<k e b(n)b(k)>knk, da cui risulta che k non è immagine di alcun numero naturale secondo b.

Ora, se ogni successione strettamente crescente non banale ha come immagine un sottoinsieme stretto di , possiamo considerare il complementare della sua immagine in , H=\F(), che sarà un insieme non vuoto e quindi (in quanto sottoinsieme di ) totalmente ordinato e numerabile; in soldoni, in tale complementare possiamo considerare il primo elemento (inteso come il minimo), il secondo elemento (il più piccolo elemento di H maggiore del primo elemento), etc.

La seconda condizione su F ci dice quindi che il primo elemento di H è esattamente F(F(1))+1, che il secondo elemento di H è F(F(2))+1, etc. Volendo, la cosa si può riformulare dicendo che H è l'immagine della successione h(n)=F(F(n))+1.

La domanda a questo punto è se effettivamente esiste (almeno) una successione F che soddisfi i requisiti prescritti, e (in caso affermativo) se tale successione sia unica. Vi sono vari approcci per trovare risposta alla domanda, ed uno dei più immediati è sicuramente quello costruttivo: dimostriamo che F esiste ed è unica determinando i valori di F per ogni n e mostrando come essi siano univocamente determinati.

Nel procedimento, ci serviremo di due ulteriori osservazioni. La prima è che in una successione strettamente crescente di numeri naturali a si ha sempre3 a(n)n; la seconda è che nel complementare H del codominio di F non possono esservi mai due interi consecutivi (infatti, se kH, avremo k-1=F(F(n)) per un opportuno n, e quindi k-1, essendo nell'immagine di F, non starà in H).

Costruiamo dunque la nostra F, e vedremo come nel farlo costruiremo di necessità anche H (ovvero, come visto, equivalentemente, la successione h dei valori non assunti da F).

Abbiamo innanzi tutto che F(1)=1. Se così non fosse, infatti, sarebbe 1H; di più, 1 sarebbe il primo elemento di H (non possono infatti esservi in H numeri più piccoli), e quindi dovrebbe essere (per la seconda proprietà di F) 1=F(F(1))+1, da cui risulterebbe 0=F(F(1))F(1)1 (dove le due disuguaglianze sono ottenute dalla precedente osservazione su valori e indici delle successioni crescenti).

Da F(1)=1 segue che F(F(1))=F(1)=1 e quindi h(1)=2: il primo elemento di H è 2, e quindi F(2)3 (per la crescenza di F abbiamo F(2)2, ma 2HF(2)2).

Possiamo anzi dire che F(2)=3: se infatti fosse F(2)>3, dalla crescenza di F seguirebbe che F(n)>3n>1, che in congiunzione con il fatto che F(1)=1<3 ci direbbe che 3 non è immagine di alcun elemento, e quindi 3H, ma ciò è impossibile, essendo 2H e non potendosi avere, come osservato, numeri consecutivi in H.

Quindi F(2)=3, da cui segue che F(3)4 (stretta crescenza di F), e quindi il secondo elemento di H sarà h(2)=F(F(2))+1=F(3)+15 e quindi h(n)5n>1, per cui 4H e, per complementareità 4F(); sarà quindi4 F(3)=4, da cui infine h(2)=5.

Così procedendo possiamo calcolare manualmente ciascun valore di F e di h, ottenendo qualcosa come la seguente (l'idea, in soldoni, è di ‘riempire’ i valori di F finché possibile, e quindi quelli di h secondo la formula della seconda condizione):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24
h 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39

Se questa tecnica costruttiva ci può servire come prova dell'esistenza (ed unicità) della F (e della relativa h), non sembra dirci molto sulla sua forma chiusa.

Possiamo però studiare i primi termini delle due successioni F ed h e notare ad esempio che —almeno nella sequenza iniziale— esibiscono questo tipo di comportamento:

  • per F, valori successivi differiscono tra loro di 1 o 2 (più spesso 2 che 1) unità;
  • per h, invece, i ‘passi’ tra un valore e il successivo sono di 2 o 3 (più spesso 3 che 2) unità.

Le successioni di Beatty

Il comportamento in questione è tipico delle successioni di Beatty, una classe di successioni il cui termine generico ha la forma nϑ per un fissato ϑ numero reale positivo irrazionale (il simbolo rappresenta la funzione ‘parte intera’). Se ϑ>1, la successione è strettamente crescente, e la differenza tra due termini consecutivi è sempre compresa tra ϑ e ϑ+1.

Una interessante proprietà delle successioni di Beatty è che se α e β sono irrazionali positivi tali che 1α+1β=1, allora le rispettive successioni di Beatty partizionano i numeri naturali (ovvero, sono complementari e la loro unione è data dall'intero insieme ).

Vi sono forti indizi che le nostre successioni F e h siano successioni di Beatty complementari. Per risolvere il nostro problema basterebbe quindi trovare una coppia di numeri irrazionali α,β che soddisfino 1α+1β=1 e che generino rispettivamente F,h soddisfacenti la famosa seconda proprietà, scrivibile come h(n)=F(F(n))+1n.

Per trovare i generatori in questione cominciamo con l'osservare che, secondo quanto osservato finora, il generatore α di F dovrebbe essere compreso tra 1 e 2, mentre il generatore β di h sarebbe compreso tra 2 e 3. Da 2<β<3 e 1α+1β=1 seguirebbe anzi che 32<α<2 (da cui si potrebbe già intuire chi possa essere α, essendovi un famosissimo numero irrazionale proprio in quell'intervallo —ma noi cercheremo di essere più formali).

Partiamo quindi dalla famosa seconda proprietà, che scritta in forma esplicita nel caso di F,h successioni di Beatty ci dice che per ogni positivo n risulta nβ=nαα+1, ovvero nβ=nαα+1, e quindi -1<nβ-(nαα+1)<1, da cui ancora 0<nβ-nαα<2.

Essendo α irrazionale e positivo possiamo scrivere (n-1)α<nα<nα, e quindi spezzare l'ultima catena di diseguaglianze in nβ-(n-1)α2>nβ-nαα>0 e nβ-nα2<nβ-nαα<2. Dividendo per n ovunque e portando un α2n a minorare nella prima diseguaglianza otteniamo infine la relazione α2n<β-α2<2n vera per ogni n, da cui in definitiva β-α2=0 e quindi β=α2.

Abbiamo quindi che α,β devono soddisfare 1α+1β=1 e β=α2. Sostituendo nella prima abbiamo 1α+1α2=1 o α+1=α2, la cui unica soluzione positiva è la famosa sezione aurea φ=1+52.

In definitiva, abbiamo dimostrato che se una coppia di successioni di Beatty complementari soddisfa le condizioni richieste, allora dovrebbe avere come generatori φ e φ2. Per concludere che le successioni di Beatty con questi generatori sono effettivamente quelle che cercavamo rimane ora da verificare che esse soddisfano i due criteri5.

La crescenza di F è immediata conseguenza del fatto che il generatore è maggiore di 1, quindi rimane da provare la famosa seconda condizione, che vista la complementareità delle successioni possiamo esprimere così: dimostrare che per ogni n risulta nφ2=nφφ+1.

Osserviamo innanzi tutto che, posto k(n)=nφ-(n-1)φ, risulta nφ2-(n-1)φ2=k(n)+1. Infatti, essendo φ2=φ+1, possiamo scrivere nφ2=nφ+n e (n-1)φ2=(n-1)φ+n-1; sottraendo membro a membro otteniamo nφ2-(n-1)φ2=nφ-(n-1)φ+1=k(n)+1.

Abbiamo quindi che nφ2=(n-1)φ2+k(n)+1, e per provare la nostra tesi basta dimostrare che nφφ=(n-1)φ2+k(n), eguaglianza che possiamo riscrivere nφ(1+1φ)=(n-1)(φ+1)+k(n), ovvero nφ+nφφ=(n-1)φ+n-1+k(n). Essendo nφ=(n-1)φ+k(n) la nostra tesi si semplifica nel dover dimostrare che nφφ=n-1 o equivalentemente6 n-1nφφ<n che possiamo riscrivere (n-1)φnφ<nφ.

La diseguaglianza di destra è immediata essendo φ irrazionale, rimane quindi da provare che (n-1)φnφ. Supponiamo per assurdo che sia vero il contrario, ovvero (n-1)φ>nφ, da cui seguirebbe (n-1)φnφ; ma (n-1)φ<nφ, quindi (n-1)φnφ, e pertanto (n-1)φ=nφ, che implica nφ-(n-1)φ<1, ovvero φ<1, assurdo7.

Abbiamo così completato la nostra dimostrazione e verificato che le successioni di Beatty con generatori φ e φ2 sono effettivamente quelle cercate.

Le successioni di Wythoff

Queste due successioni sono meglio note come la successione inferiore (F) e superiore (h) di Wythoff. Queste due successioni sono state scoperte appunto dall'eponimo matematico nello studiare un famoso problema di teoria dei giochi che prende vari nomi (problema di Wythoff, il gioco delle scatole dei biscotti, etc).

Il gioco ha la seguente forma: ci sono due scatole di biscotti, e due giocatori si alternano scegliendo quanti biscotti vogliono da una sola delle due scatole, oppure lo stesso numero di biscotti da entrambe le scatole. Vince il giocatore che prende l'ultimo biscotto.

È evidente che se una delle due scatole è vuota, o se ambo le scatole hanno lo stesso numero di biscotti, il primo giocatore vince. Il gioco si fa più interessante se entrambe le scatole sono piene ed il numero di biscotti non è equamente distribuito.

Ad esempio, se le scatole hanno rispettivamente 1 biscotto e 2 biscotti, è evidente che il secondo giocatore vincerà, qualunque sia la scelta fatta dal primo giocatore. Ovviamente, partendo da un'altra configurazione, un giocatore dovrebbe quindi cercare di arrivare alla distribuzione 1/2 per aver garantita la vittoria. La domanda è: quali altre configurazioni hanno tale proprietà? Ovvero, quali coppie di numeri (a,b) sono tali che, qualunque sia la mossa del primo giocatore, il secondo si può garantire la vittoria?

Con un poco di calcoli si scopre che le coppie (ordinate, con a<b) che garantiscono la vittoria al giocatore che le raggiunge sono

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24
b 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39

e se la tabella vi ricorda qualcosa è perché i valori sono esattamente gli stessi visti nella precedente tabella: le coppie (F(n),h(n)) sono le configurazioni vincenti nel problema di Wythoff.

Una nota finale

Concludiamo questa nostra rapida escursione sulla questione osservando che h(n) ha una forma ben più semplice della già vista F(F(n))+1, e questa è h(n)=F(n)+n. La cosa, chiaramente visibile dai valori in tabella e facilmente dimostrabile8, ci permette di leggere le successioni di Wythoff in questo modo: ogni coppia (F(n),h(n)) è la coppia vincente in cui la differenza di contenuto tra le due scatole di biscotti è pari ad n.

Questo, combinato con la proprietà di partizionamento di di cui godono le due successioni (ogni intero sta in una ed una sola delle successioni, e quindi anche in una ed una sola coppia) e con il fatto che il gioco è puramente ‘sottrattivo’ (da una configurazione all'altra si passa solo diminuendo uno o entrambi dei contenuti) è sufficiente a definire la strategia vincente, che viene lasciata come esercizio per il lettore.


  1. si intende qui l'insieme dei numeri interi strettamente positivi. ↩  ↩

  2. l'affermazione è ovvia nel caso k=1, poiché non vi sono numeri naturali1 minori di 1; se invece k>1, posto l=b(k) e supponiamo per assurdo l<k: essendo b(n)=nn<k per la scelta di k, avremmo, b(k)=l=b(l), e quindi b(l)=b(k) con l<k, che viola la stretta crescenza di b. ↩

  3. si dimostra ad esempio per induzione. Come base induttiva abbiamo che a(1)a(1)1. Supponiamo ora che a(n)n e dimostriamo che da questo segue a(n+1)n+1: per la stretta crescenza della successione abbiamo a(n+1)>a(n)n, ovvero a(n+1)>n, e non essendovi numeri naturali tra n ed n+1 questo equivale ad a(n+1)n+1. ↩

  4. se fosse F(3)>4, per la crescenza di F si avrebbe F(n)>4n>3, da cui, sapendo che F(1)<4 ed F(2)<4, seguirebbe che 4F(). ↩

  5. tale verifica è necessaria perché l'ipotesi da noi fatta (ovvero che F ed h siano successioni di Beatty complementari) potrebbe condurre ad un assurdo, da cui seguirebbe che in realtà esse non sono successioni di Beatty. ↩

  6. si ha x=m se e solo se mx<m+1, da applicare nel nostro caso con x=nφφ,m=n-1 ↩

  7. osserviamo che per un arbitrario numero reale positivo α la diseguaglianza (n-1)αnα non è in genere verificata, come si vede prendendo ad esempio α=1K per un fissato K naturale ed osservando che per ogni 1<n<K si ha nα=nK=0<n-1K=(n-1)α; la diseguaglianza è però verificata per tutti i numeri reali α1. ↩

  8. essendo nota la forma esplicita delle due successioni, ci basta provare che nφ2=nφ+n; partiamo quindi dall'equazione che definisce la sezione aurea: da φ2=φ+1 segue, per ogni n, nφ2=n(φ+1) e quindi anche nφ2=nφ+n, o equivalentemente nφ2=nφ+n, ciò che volevamo dimostrare. ↩