Prendiamo un razionale $ x_1\ge 1 $
Poniamo per ogni $ n\ge 1 $:
$ \displaystyle x_{n+1}=x_n+\frac{1}{[x_n]} $
Dove $ [x_n] $ e' il piu' grande intero non maggiore di $ x_n $
Dimostrare che esiste un k tale che $ x_k\in\mathbb{Z} $
Successione russa
Successione russa
"Sei la Barbara della situazione!" (Tap)
Giusto butto giù qualche idea.
Chiediamoci cosa succede quando cambia la parte intera di $ \displaystyle x_n $, diciamo che cambia da a ad a+1.
Appena ho cominciato ad aggiungere degli 1/a, la parte razionale di $ \displaystyle x_n $ era compresa tra 0 e 1/(a-1). Quindi per cambiare parte intera devo aggiungere a-1 volte oppure a volte la frazione 1/a.
- se la ho aggiunta a volte, allora la parte razionale della sequenza, dopo questi a cambi, non è cambiata. Diciamo che questo è un passaggio buono.
- se la ho aggiunta a-1 volte, diciamo che è un passaggio cattivo. Un passaggio cattivo capita se e soltanto se, la prima volta che ho aggiungo 1/a, la parte razionale della sequenza era compresa tra 1/a ed 1/(a-1). Alla fine del passaggio cattivo, la parte razionale della sequenza è compresa tra 0 e $ \displaystyle \frac 1 {a-1} - \frac 1a = \frac 1 {a(a-1)} $.
Cerchiamo di stimare quanti passaggi buoni o cattivi capitano. Sappiamo che dopo un passaggio cattivo ci troviamo con una parte razionale tra 0 e 1/a(a-1), e con una parte intera a+1. Ad ogni passo buono la parte razionale rimane costante, e perchè ci sia un passo cattivo dobbiamo trovarci con una parte intera maggiore di a(a-1). Quindi, diciamo, almeno da a+1 ad a^2-a abbiamo passi buoni. Quindi circa a^2-2a-1 passaggi buoni.
Cerchiamo di stimare che danni provoca un passo cattivo. Un passo cattivo che lascia una parte intera di a+1, il peggior danno che può fare, è moltiplicare il denominatore di x_n per a.
Ora cerchiamo di capire quando si vince: ad esempio, quando la parte intera di x_n supera il denominatore di x_n, abbiamo vinto.
Ricapitolando: abbiamo un passo cattivo che moltiplica il denominatore per a, e poi la parte intera viene aumentata circa a^2-2a volte senza che il denominatore aumenti.
Bene, finora ero formalissimo, ora invece vado molto a spanne.
Mettiamoci subito nel caso peggiore, dove ogni passaggio cattivo ci moltiplica il denominatore per a, e dove ogni passaggio cattivo capita il prima possibile. (il problema sarebbe dimostrare che questo è il caso peggiore...)
Ora, sia d il denominatore di partenza, a una parte intera da cui decidiamo di partire. Definiamo p(a) ) x^2-2a.
Dopo n passaggi cattivi il denominatore sarà qualcosa del tipo:
$ \displaystyle dap(a)p^2(a)p^3(a)\cdots p^{n-1}(a) $ (1)
E subito dopo il n+1-esimo passaggio cattivo la parte intera sarà qualcosa tipo $ \displaystyle p^n(a) $.
Ora, visto che la formula (1) ha grado 1+2+4+8+... = 2^n - 1, e che $ \displaystyle p^n(a) $ ha grado 2^n, io direiche a lungo andare la vincono i buoni
Chiediamoci cosa succede quando cambia la parte intera di $ \displaystyle x_n $, diciamo che cambia da a ad a+1.
Appena ho cominciato ad aggiungere degli 1/a, la parte razionale di $ \displaystyle x_n $ era compresa tra 0 e 1/(a-1). Quindi per cambiare parte intera devo aggiungere a-1 volte oppure a volte la frazione 1/a.
- se la ho aggiunta a volte, allora la parte razionale della sequenza, dopo questi a cambi, non è cambiata. Diciamo che questo è un passaggio buono.
- se la ho aggiunta a-1 volte, diciamo che è un passaggio cattivo. Un passaggio cattivo capita se e soltanto se, la prima volta che ho aggiungo 1/a, la parte razionale della sequenza era compresa tra 1/a ed 1/(a-1). Alla fine del passaggio cattivo, la parte razionale della sequenza è compresa tra 0 e $ \displaystyle \frac 1 {a-1} - \frac 1a = \frac 1 {a(a-1)} $.
Cerchiamo di stimare quanti passaggi buoni o cattivi capitano. Sappiamo che dopo un passaggio cattivo ci troviamo con una parte razionale tra 0 e 1/a(a-1), e con una parte intera a+1. Ad ogni passo buono la parte razionale rimane costante, e perchè ci sia un passo cattivo dobbiamo trovarci con una parte intera maggiore di a(a-1). Quindi, diciamo, almeno da a+1 ad a^2-a abbiamo passi buoni. Quindi circa a^2-2a-1 passaggi buoni.
Cerchiamo di stimare che danni provoca un passo cattivo. Un passo cattivo che lascia una parte intera di a+1, il peggior danno che può fare, è moltiplicare il denominatore di x_n per a.
Ora cerchiamo di capire quando si vince: ad esempio, quando la parte intera di x_n supera il denominatore di x_n, abbiamo vinto.
Ricapitolando: abbiamo un passo cattivo che moltiplica il denominatore per a, e poi la parte intera viene aumentata circa a^2-2a volte senza che il denominatore aumenti.
Bene, finora ero formalissimo, ora invece vado molto a spanne.
Mettiamoci subito nel caso peggiore, dove ogni passaggio cattivo ci moltiplica il denominatore per a, e dove ogni passaggio cattivo capita il prima possibile. (il problema sarebbe dimostrare che questo è il caso peggiore...)
Ora, sia d il denominatore di partenza, a una parte intera da cui decidiamo di partire. Definiamo p(a) ) x^2-2a.
Dopo n passaggi cattivi il denominatore sarà qualcosa del tipo:
$ \displaystyle dap(a)p^2(a)p^3(a)\cdots p^{n-1}(a) $ (1)
E subito dopo il n+1-esimo passaggio cattivo la parte intera sarà qualcosa tipo $ \displaystyle p^n(a) $.
Ora, visto che la formula (1) ha grado 1+2+4+8+... = 2^n - 1, e che $ \displaystyle p^n(a) $ ha grado 2^n, io direiche a lungo andare la vincono i buoni