L[04] Contoso, ma anche bello

[Gerald Lambeau]

Definiamo una sequenza $f(1), f(2), \dots, f(i), \dots$ di interi positivi dove $f$ è calcolata, per ogni $n$ intero positivo, al seguente modo:
$f(1)=1$
$f(n)=\begin{cases} f(n-1)-n & \mbox{se }f(n-1)>n \\ f(n-1)+n & \mbox{se }f(n-1) \le n
\end{cases}$
per $n \ge 2$.
Sia $S= \left\{ n \in \mathbb{N} | f(n)=a \right\}$ dove $a$ è un intero positivo dato.
(i) Mostrare che $S$ ha infiniti elementi.
(ii) Siano $n_1<n_2<n_3<\dots$ gli elementi di $S$. Mostrare che $\displaystyle \lim_{j \rightarrow \infty} \frac{n_{i+1}}{n_i}=3$.
(iii) Calcolare $n_1$ per $a=2017$.

[ElPaso98]

Provo la soluzione del primo e nel dubbio chiedo un hint per gli altri punti (non c'ho ancora provato ma non mi sembrano troppo immediati)

Testo nascosto:

Siano [tex]k,h \in \mathbb{N}[/tex] diversi da [tex]0[/tex]. Sia [tex]f(k)=1[/tex]. Consideriamo due elementi della successione tali che [tex]f(k+2h+2)>f(k+2h+1)\rightarrow f(k+2h+1)\le k+2h+2[/tex] (ad esempio [tex]f(k+4)=2k+5[/tex] e [tex]f(k+3)=k+1[/tex], si ha dunque che [tex]f(k+2h+3)<f(k+2h+2)[/tex] poichè [tex]f(k+2h+3)<k+2h+2+f(k+2h+1)\rightarrow f(k+2h+1)>1[/tex] per l'ipotesi [tex]h\not=0[/tex], allora [tex]f(k+2h+3)=f(k+2h+2)-(k+2h+3)=f(k+2h+1)+k+2h+2-(k+2h+3)=f(k+2h+1)-1[/tex]. Di conseguenza [tex]f(k+2h+4)=k+2h+4+f(k+2h+1)-1=f(k+2h+2)+1[/tex], (si somma in quanto [tex]f(k+2h+3)<f(k+2h+1)\le k+2h+2<k+2h+4)[/tex].
Tutto questo a parole signfica che se [tex]f(k)=1[/tex], allora [tex]f(k+pari)[/tex] parte da [tex]2k+4[/tex] e sale di [tex]1[/tex], mentre [tex]f(k+dispari)[/tex] parte da [tex]k+2[/tex] e scende di [tex]1[/tex] ogni volta, allora scendendo prende tutti i valori naturali da [tex]k+2[/tex] fino a [tex]1[/tex] per poi ricominciare in modo analogo,
quindi ogni [tex]a[/tex] viene assunto dalla funzione infinte volte.

[Gerald Lambeau]

In soldoni è giusta, però devo dire che mi sono un po' perso nei tuoi passaggi. Allora, correzione al volo:
- non poni nessun limite su $h$, eppure sai che prima o poi la funzione troverà un $k'$ tale che $f(k')=1$, quindi i numeri che tu consideri prima o poi si fermeranno (per poi ricominciare). L'hai detto, ma è meglio esprimerlo anche matematicamente;
- i passaggi sono spiegati brevemente o non spiegati: le formule date dalle ipotesi devono essere scritte e deve essere spiegato perché valgono in questo o in quel caso, sinceramente non avevo voglia di stare a verificare che ogni formula venisse da quelle, e credimi che potresti trovare un correttore che, poiché non hai spiegato ogni cosa dettagliatamente, non te lo valuti;
- dai per scontato che $f(k+x+1)>f(k+x)$ quando $x$ è dispari, ma non lo dimostri. L'hai più o meno indotto nei passaggi successivi, che mantengono questa relazione, ma comunque senza un caso base non è sufficiente.
Per il resto, a meno di errori che non ho visto, se quello che fai è giusto e l'hai verificato allora è corretta, solo un po' confusionaria e con qualche mancanza, ecco tutto.

Per il punto (ii): da un certo punto in poi ti devi preoccupare solo di $f(k+pari)$ (perché?), a questo punto ti serve una formula esplicita; spiego meglio: da un certo punto in poi $n_i$ e $n_{i+1}$ saranno dati uno da un certo $k$ e uno dal successivo perché ci sarà esattamente un valore buono per ogni $k$ tale che $f(k)=1$, quindi fissato un $k$ ti trovi il relativo $h=g(k, a)$ che funziona e sai quant'è il relativo $n_i$, analogamente ti trovi il successivo. Dopo è tutta algebra e rimaneggiamenti per far venire fuori la cosa che vuoi. L'unico problema è che devi riuscire a esplicitarti $h$, che con quello che dici in fondo dovresti riuscire a fare. Ah, e dovresti riuscire a trovarti anche il $k$ successivo, o in generale l'$m$-esimo $k$ in funzione di $m$. Sì, lo ammetto, questa è la parte più contosa di tutto il problema, ma è anche bella!

Il punto (iii) è veramente semplice, si ragiona con un po' di disuguaglianze e tentativi, ma mi sa che come sopra ti conviene avere una formula che ti generi tutti i $k$, altrimenti non sai dove andare a cercare!

[ElPaso98]

1)Grazie della correzione, so che è molto pesante come soluzione, me ne sono accorto mentre scrivevo io stesso quindi alcuni conti li ho saltati totalmente o buttati lì senza starci troppo a spiegarli, la cosa che mi preme di più è cercare di renderla più valida proprio a livello matematico, sicuramente a quel punto risulterà più scorrevole
2)Grazie degli hint

[Gerald Lambeau]

Prego!