Definiamo la funzione $ f : \mathbb{N} \to \mathbb{N} $ come $ f(2n)=2f(n)+1 $ ed $ f(2n+1)=2f(n) $ e ponendo $ f(0)=f(1)=0 $. Per ogni $ m $ intero definiamo poi una successione $ a_k $ ponendo $ a_0=m \ \ \wedge a_{k+1}=f(a_k) $.
(a) DImostrare che qualunque sia $ m $ la successione diventa nulla da un certo punto in poi.
(b)Determinare il più piccolo valore di $ m $ per cui il primo valore della successione ad essere nullo è il $ 2002 $-esimo.
Metto la mia soluzione in hidden text , molto più sul tipo "flusso di coscienza" che soluzione ufficiale: io ci sono andato giù di casi per poi provare a formalizzare il tutto e non so neanche bene con quali risultati ma magari c'è una strategia più semplice quindi boh può essere interessante vedere come si è ragionato più che il semplice risultato e se ci sia una tecnica più immediata.
Testo nascosto:
Allora prima cosa sporchiamoci le mani e vediamo come funziona questa cosa. $ f(2)=1, \ \ f(3)=0, \ \ f(4)=3, \ \ f(5)=2 , \ \ f(6)=1, \ \ f(7)=0 $. La cosa già è buona perchè la funzione si annulla ma oltrettutto notiamo una certa regolarità : come se scalasse con un "periodo" di $ 2^k $ decrescendo per ogni $ k $ e proviamo allora a dimostrare detto in linguaggio decente che definito $ n=2^h+x $ con $ 0<x < 2^h $si ha $ f(n)=2^h-x-1 $.
Dobbiamo però prima levarci il caso $ n=2^k $ per definirla completamente .
Allora per induzione su $k$ dimostriamo che $f(2^k)=2^k-1$.Si ha $f(2)=2f(1)+1=1$ come voluto e passando da $k-1$ a $k$ si ha $f(2^k)=2f(2^{k-1})+1=2^k-1$.
Ora procediamo a dimostrare il nostro claim iniziale sempre per induzione(se volete ristretta ad un certo intervallo di $2^h$). Passo base: $x=1$. Allora si ha $f(2^h+1)=2f(2^{h-1})=2^h-2$ proprio come voluto.
Passiamo ora da $x$ a $x+1$ tenendo conto che nel caso $n=2^h+2^h-1$ andremmo a finire in $n=2^{h+1}$ da noi definito e dimostrato precedentemente in altro modo. Ora sia $x=2k$ in tal caso per come è definita la funzione dato $f(2n+1)=f(2n)-1$ la tesi è a posto.
COn $x=2k+1$ si ha che $ f(2^h+2k+2)=2f(2^{h-1}+k+1)+1$ . Ora (questo passaggio non so quanto sia corretto) tutti i ragionamenti che abbiamo fatto prescindono dalla $h$. Ma sappiamo sicuramente che vale $0<2k<x $ e dato $x<2^h$ si ha $k <2^{h-1}$. Si possono allora usare le ipotesi induttive ottenendo $ f(2^h+2k+2)=2(2^{h-1}-k-2)+1=2^h-2k-3 $ come voluto.
Allora quella degli $a_k$ è una sequenza decrescente nonnegativa in quanto si è appena visto che $0<f(n)<n \forall n \ \geq 1$. Dobbiamo avere allora o un minimo che poi "cicla" facendo riavere lo stesso valore o si deve arrivare a $0$ ma il minore è stretto quindi abbiamo vinto.
Ora per la parte (b). La prima idea è dare una stima di come questa robba debba andare. Sicuramente deve valere $a_{2000}=2^k $ e $a_{2001}=2^k-1$. Ora l'idea è che per ottenere dalla funzione un certo valore $2^h+x$ con la stessa definizione di prima devo muovermi in untervallo del tipo $(2^{h+1},2^{h+2})$. Per cui la scelta di $a_{1999}$ e via dicendo fino ad $a_0$ dipende da quel $k$ sopra indicato da cui per minimizzare $m$ poniamo $k=1$.
Ora definiamo una nuova successione per cui $b_0=2$ e $b_i=f(b_{i+1})$. Ora qui l'idea era trovare una successione $b_i=a_{2000-i}$ con quella regola in cui potessi trovarmi i valori partendo dal mio $a_0$ che abbiamo detto essere $=2$ e minimizzare $a_{2002}$ così. Effettivamente la successione $b_k$ definita come sopra funziona ma bisogna trovare una formula chiusa per arrivare al minimo e far rispettare la ricorrenza. Dopo una certa serie di tentativi infruttuosi ci si rende conto che va bene e ci risolve tutto la successione così definita:
$\displaystyle b_{2k}=\sum_{i=0}^k 2^{2i+1}$ e $ \displaystyle b_{2k+1}=\sum_{i=0}^{k+1} 2^{2i} $. Difatti dimostriamo quella robba funziona cioè rispetta la ricorrenza ed è minima.
Prima di tutto verifichiamo che quella robba non faccia mai $2^a-1$ per qualche $a$ in modo da non annullarsi prima del tempo. I $b_i$ con indice pari sono pari quindi non possono essere. Per quelli con indice dispari notiamo che $i=2k+1$ e $a<2k+1$ allora $b_i$ è sicuramente maggiore di $2^a-1$. Ma d'altro canto se $a>2k+1$ si ha che $\displaystyle 2^a-1= \sum_{i=0}^{a-1} 2^i >\sum_{i=0}^k 2^{2i+1}$ e si ha quanto voluto.
Abbiamo già notato che perchè un certo $b_i$ sia minimo deve valere $ 2^{i+1}<b_i<2^{i+2} $.Esistono infatti altri valori ottenuti con "periodi" di potenze di $2$ ma saranno sicuramente maggiori. Verifichiamo allora che $ \displaystyle 2^{2k+1}<\sum_{i=0}^k 2^{2i+1}<2^{2k+2} $. Ma dato che vale $ \displaystyle 2^{2k+2} > \sum_{i=0}^{2k+1} 2^i >\sum_{i=0}^k 2^{2i+1} $ stiamo pace. Applichiamo la stessa disuguaglianza sul caso dispari e si vince.
Ci resta da dimostrare allora che questa robba rispetti la ricorrenza . Andiamo giù di induzione su $k$. Passo base . Analizziamo caso dispari e pari in parallelo. Si ha $f(b_2)=f(10)=b_1$ e analogamente $f(b_1)=f(5)=b_0$.
Mo supponiamo la tesi sia vera per pari e dispari fino ad un certo $k-1$ e andiamo in $k$ si deve scomporre : $ \displaystyle b_{2k}=\sum_{i=0}^k 2^{2i+1}= 2 \sum_{i=0}^k 2^{2i} \ \ \Rightarrow f(2 \sum_{i=0}^k 2^{2i})= 2f(\sum_{i=0}^k 2^{2i})+1$ che per induzione trasformiamo in $\displaystyle 2(\sum_{i=0}^{k-1} 2^{2i+1})+1= \sum_{i=0}^{k} 2^{2i}$.
Facciamo il caso analogo sfruttando la definizione per i dispari e ci esce $ \displaystyle f(1+\sum_{i=1}^{k+1} 2^{2i})=2f(\sum_{i=1}^{k+1} 2^{2i-1})=2f(\sum_{i=0}^{k} 2^{2i+1})=2(\sum_{i=0}^{k} 2^{2i}) $ ottenendo quanto voluto. L'ultimo passaggio discende da quanto appena dimostrato per i pari.
Ci resta solo da individuare questo benedetto valore. SI ha $\displaystyle b_{2000}= \sum_{i=0}^k 2^{2i+1}= 2 (\sum_{i=0}^k 2^{2i})= 2(\sum_{i=0}^k 4^{i})= 2\frac{4^{1000}-1}{3}$
Cristo è l'unica soluzione reale. Tutte le altre sono complesse coniugate
Un corpo maleducato immerso in un liquido jastemma.
Una tecnica più immediata c'è, ed è suggerita da tutti quei due nella ricorsione... prova a risolverlo, se ti serve aiuto chiedi pure!
Hint non criptico: