Esiste una funzione dagli interi positivi agli interi positivi tale che:
$ $\begin{cases}
f(1)=2\\
f(f(n))=f(n)+n \text{ per ogni } n\\
f(n)<f(n+1) \text{ per ogni } n \text{ ?}\\
\end{cases}$ $
IMO 1993 - 5
Pongo {$ a_i $} la successione tale che $ a_0=1 $ e $ a_j = f(a_{j-1}) $ $ \forall j \in \mathbb N $, allora si ha che $ a_j = a_{j-2} + a_{j-1} $ $ \forall j \in \mathbb N $, tale successione corrisponde alla successione di Fibonacci (a cui sono tolti lo 0 iniziale e il primo dei due 1) se $ a_0=1 $ e $ a_1=2 $, dunque l'unica successione definita dall'ipotesi è proprio la successione di Fibonacci.
Sono ancora da definire le successioni che iniziano per numeri che non compaiono in quella di Fibonacci (per esempio non sappiamo quanto vale $ f(4) $, ma sappiamo che può valere 6 o 7 per la terza condizione in ipotesi), ma queste successioni si possono sempre definire a piacere, infatti man mano che si va avanti con le successioni esistenti, aumenta il numero dei numeri da definire in quanto aumenta lo spazio tra i numeri in successioni definite (in ogni modo scegliendo f(k) per un valore k compreso tra due numeri in modo che f(k) sia compreso tra le funzioni di quei due numeri, l'intera successione rispetterà la condizione n° 3, questo lo si dimostra per induzione (ora non ho il tempo di farlo)), quindi è possibile scegliere le successioni in infiniti modi.
P.s. Se trovate qualche errore nella mia soluzione fatemelo notare please.
Sono ancora da definire le successioni che iniziano per numeri che non compaiono in quella di Fibonacci (per esempio non sappiamo quanto vale $ f(4) $, ma sappiamo che può valere 6 o 7 per la terza condizione in ipotesi), ma queste successioni si possono sempre definire a piacere, infatti man mano che si va avanti con le successioni esistenti, aumenta il numero dei numeri da definire in quanto aumenta lo spazio tra i numeri in successioni definite (in ogni modo scegliendo f(k) per un valore k compreso tra due numeri in modo che f(k) sia compreso tra le funzioni di quei due numeri, l'intera successione rispetterà la condizione n° 3, questo lo si dimostra per induzione (ora non ho il tempo di farlo)), quindi è possibile scegliere le successioni in infiniti modi.
P.s. Se trovate qualche errore nella mia soluzione fatemelo notare please.
[tex] \lambda \upsilon \iota \varsigma [/tex]
La prima parte va bene, hai dimostrato che, se f esiste, sull'n-esimo numero di Fibonacci fa l'n+1-esimo numero di Fibonacci. Per il resto non hai dimostrato niente, hai solo notato che è verosimile che le cose funzionino. Devi far vedere che è effettivamente possibile "riempire i buchi", oppure dimostrare che è impossibile. Inoltre, non è esatto dire che la funzione è univocamente determinata solo sui Fibonacci, o almeno non lo è a priori. Per farti un esempio, se vuoi una funzione dai naturali ai naturali che sia strettamente crescente e sia l'identità sui numeri pari, a prima vista è definita solo sui numeri pari, ma in realtà lo è anche sui dispari. Oppure, visto che, definita la funzione su un numero "libero", è automaticamente definita su tutta una "successione di Fibonacci generalizzata", è possibile che scegliendo male un valore della funzione, prima o poi due successioni si incontrino con valori diversi. In sintesi, formalizza quel pezzo che dici che si può fare per induzione .
Ok, ora che ho tempo dimostro ciò che volevo dimostrare per induzione:
Supponiamo di avere tre valori $ A<B<C $, tali che $ f(A) < f(C) $ sono valori determinati e $ f(B) $ è ancora da determinare, si può scegliere un valore per $ f(B) $ qualsiasi, purché compreso tra $ f(A) $ e $ f(C) $, dimostriamo che comunque si scelga $ f(B) $, $ f(f(B)) $ è sempre compreso tra $ f(f(A)) $ e $ f(f(C)) $, possiamo esprimere
B come $ A+n $ e C come $ A+n+m $, con $ m,n \in \mathbb N $, e poiché $ f(A) < f(B) < f(C) $, possiamo porre $ f(B) = f(A) + p $ e $ f(C)= f(A) +p +q $ con $ p,q \in \mathbb N $, allora scriviamo:
$ f(f(A)) = f(A) + A $
$ f(f(B)) = f(A) + p + A + n= f(f(A)) +p +n $
$ f(f(C)) = f(A) +p+q +A+m+n = f(f(B)) +q+m $
Analogamente si dimostra che, date tre successioni {$ x_i $}, {$ y_i $} e {$ z_i $}, se $ x_0 < y_0<z_0 $, allora $ x_j<y_j<z_j $ $ \forall j \in \mathbb N $.
Supponiamo di avere tre valori $ A<B<C $, tali che $ f(A) < f(C) $ sono valori determinati e $ f(B) $ è ancora da determinare, si può scegliere un valore per $ f(B) $ qualsiasi, purché compreso tra $ f(A) $ e $ f(C) $, dimostriamo che comunque si scelga $ f(B) $, $ f(f(B)) $ è sempre compreso tra $ f(f(A)) $ e $ f(f(C)) $, possiamo esprimere
B come $ A+n $ e C come $ A+n+m $, con $ m,n \in \mathbb N $, e poiché $ f(A) < f(B) < f(C) $, possiamo porre $ f(B) = f(A) + p $ e $ f(C)= f(A) +p +q $ con $ p,q \in \mathbb N $, allora scriviamo:
$ f(f(A)) = f(A) + A $
$ f(f(B)) = f(A) + p + A + n= f(f(A)) +p +n $
$ f(f(C)) = f(A) +p+q +A+m+n = f(f(B)) +q+m $
Analogamente si dimostra che, date tre successioni {$ x_i $}, {$ y_i $} e {$ z_i $}, se $ x_0 < y_0<z_0 $, allora $ x_j<y_j<z_j $ $ \forall j \in \mathbb N $.
[tex] \lambda \upsilon \iota \varsigma [/tex]
Secondo me le idee ce le hai messe, ma come scriveresti una dimostrazione del genere in gara? Diciamo che per come l'hai scritta si capisce che hai capito, ma non è del tutto chiaro dove vai a parare.
Se vuoi un consiglio per formalizzare meglio, prova a scrivere una roba del genere:
sia A il minimo naturale tale che f(A) non è già definita, definisco f(A)=f(A-1)+1. A questo punto è molto più semplice dire quello che hai detto tu senza però incasinarsi, perchè più è intricato quello che scrivi più è facile perdere punti
Se vuoi un consiglio per formalizzare meglio, prova a scrivere una roba del genere:
sia A il minimo naturale tale che f(A) non è già definita, definisco f(A)=f(A-1)+1. A questo punto è molto più semplice dire quello che hai detto tu senza però incasinarsi, perchè più è intricato quello che scrivi più è facile perdere punti
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!
questo tra l'altro è errato, perchè se ad esempio sia A+2 che A+1 non sono già determinati e definisci f(A+2)=f(A)+1, come la definisci f(A+1) conservando la monotonia stretta?Gigi95 ha scritto: Supponiamo di avere tre valori $ A<B<C $, tali che $ f(A) < f(C) $ sono valori determinati e $ f(B) $ è ancora da determinare, si può scegliere un valore per $ f(B) $ qualsiasi, purché compreso tra $ f(A) $ e $ f(C) $
Il tempo svela ogni cosa......ma allora perchè quel maledetto problema non si risolve da solo?!