Valori possibili.

[Studente Anonimo]

Sia
\[ \mathcal{F} := \{ f: \mathbb{N} \to \mathbb{N} : f(m+n) \geq f(m) + f(f(n)) -1 , \forall n,m \in \mathbb{N} \}\]
e per \( k \in \mathbb{N} \) sia inoltre \( V(k) := \{ n \in \mathbb{N} : \exists f \in \mathcal{F},\ \text{tale che}\ f(k)=n \} \)
Dimostra che \( \forall k \in \mathbb{N} \) abbiamo che
\[ \sum_{n \in V(k)} n = \frac{(k+1)(k+2)}{2} \]

[jas1231]

faccio un tentativo:

Ipotesi
$ (i) $ $ f(m+n)ge f(m)+f(f(n))-1 $

Corollari
siccome $ f(x) ge 1 AA x in NN$ da $ (i) $ ricavo in maniera immediata i seguenti corollari:

$ (a) $ $ f(k+1)ge f(k) AA k in NN$
$ (b) $ $ f(k+1)gef(1) AA k in NN $
$ (c) $ $ f(k+1)gef(f(k)) AA k in NN $
$ (d) $ $ f(k+1)gef(f(1)) AA k in NN $

Punto 1

dimostro che $ f(k)le k+1 $:
supponiamo per assurdo che $ f(k)> k+1 $ allora

per $ (a) $ $ f $ è debolmente crescente

per $ (c) $ $ f(k+1)gef(f(k)) $

e per ipotesi $ f(k)>k+1 $

quindi possiamo affermare che

$ f(f(k))=f(k+1)=f(epsilon) AA epsilon lef(k) $ naturale

ma allora $ f(1)=f(k)>k+1 $ e per $ (i) $ scrivo

$ f(1+1)=f(2)gef(1)+f(f(1))-1=f(k)+f(f(k))-1>f(k)+k>f(k) AA k in NN$

Quindi $ f(2)nef(k) $ che è assurdo.

Punto 2

Affermo che esiste sempre almeno una funzione che rispetta l'ipotesi tale che
$ f(k)=n $ per $nin{1,2,...,k+1} $, per esempio si può costruire in questo modo

$ f(x)={ ( 1 if xk):} $ è facile verificare che questa funzione rispetta l'ipotesi.

Punto 3

Calcolo \[ \sum_{n \in V(k)} n \]

Per i punti 1 e 2 posso scrivere:

$ sum_ {n \in V(k)}n=sum_(n=1)^(k+1)n=((k+1)(k+2))/2 $

CVD

[Studente Anonimo]

"jas123":

quindi possiamo affermare che

$ f(f(k))=f(k+1)=f(epsilon) AA epsilon lef(k) $ naturale

Riesci ad argomentare meglio il motivo per cui \(f(\epsilon) = f(k+1) \) per ogni \( \epsilon \leq f(k) \)? Io direi che \( f(f(k))=f(k+1)\geq f(\epsilon) \).

"jas123":
Affermo che esiste sempre almeno una funzione che rispetta l'ipotesi tale che
$ f(k)=n $ per $nin{1,2,...,k+1} $, per esempio si può costruire in questo modo

$ f(x)={ ( 1 if xk):} $ è facile verificare che questa funzione rispetta l'ipotesi.

Il caso con \(n=k+1\) non funziona, infatti posto
\[ f(x) = \left\{\begin{matrix}
1 & \text{se} &x k+1 & \text{se} &x =k \\
x& \text{se} & x>k
\end{matrix}\right. \]
Abbiamo che
\[ 2k = f(k+k)\geq f(k) + f(f(k)) - 1 = k+1 + f(k+1) - 1 = k + k +1 = 2k +1 \]

[jas1231]

Hai ragione, ho sbagliato, però mi è venuta in mente un'altra idea, cerco di buttarla giù in maniera corretta, però è un po' difficile da esporre:

Idea generale

Noto che se $ f(k)>k+1 $ mi troverò di fronte ad una funzione con dei gradini disgiunti che avranno larghezza sempre maggiore, tuttavia per una delle proprietà delle funzioni in esame, se ci sono $ n $ elementi consecutivi uguali (del tipo che ci troveremo di fronte) allora ci saranno $ n $ elementi "iniziali" uguali a 1 cioè $ f(epsilon)=1AAepsilonin{1,2,3,...,n} $ da ciò si avrà l'assurdo.

Ipotesi

$ (i) $ $ f(m+n)ge f(m)+f(f(n))-1 $

Corollari

siccome $ f(x) ge 1 AA x in NN$ da $ (i) $ ricavo in maniera immediata i seguenti corollari:

$ (a) $ $ f(k+1)ge f(k) AA k in NN$
$ (b) $ $ f(k+1)gef(1) AA k in NN $
$ (c) $ $ f(k+1)gef(f(k)) AA k in NN $
$ (d) $ $ f(k+1)gef(f(1)) AA k in NN $

Lemma 1

Affermo che se $ f(epsilon)=f(x+1) AAepsilon in {x+1,x+2,...,f(x)} $ con $ f(x)-x=ninNN $ allora $ f(xi)=1 AAxi in {1,2,...,n} $

dimostrazione:

per $ (i) $ scrivo $ f(x+xi)gef(xi)+f(f(x))-1 AAxi in {1,2,...,n} $ ma quindi $ x+xi in {x+1,x+2,...,f(x)} $ e quindi

$ 1gef(xi)$ ma $ f(xi) in NNrArr f(xi)=1 $

Punto 1

dimostro che $ f(k)le k+1 $:

supponiamo per assurdo che $ f(k)> k+1 $ allora

per $ (a) $ $ f $ è debolmente crescente

per $ (c) $ $ f(k+1)gef(f(k)) $

e per ipotesi $ f(k)>k+1 $

allora

\( f(f(k))\geq f(k+1)\geq f(f(k)) \) e quindi $ f(k+1)=f(f(k)) $

e per $ (a) $, $ f(epsilon_1)=f(k+1) AA epsilon_1 in {k+1,k+2,...,f(k)} $
(nota: la cardinalità minima di quest'insieme è 2)

adesso per $ (i) $ scrivo

$ f(2k)gef(k)+f(f(k))-1>k+1+k+2-1=2k+2 $ , $ f(2k)>2k+2 $

per dimostrazione precedente avremo

$ f(epsilon_2)=f(2k+1)AAepsilon_2in{2k+1,...,f(2k)} $
(nota: la cardinalità minima di questo insieme è 3)

procedendo in questo modo all'infinito avremo cardinalità minima sempre maggiore, è possibile dimostrarlo per induzione in maniera simile a quanto fatto per i casi precedenti (non lo farò per risparmiare spazio ma si tratta di un banale esercizio di induzione)

ma allora avremo che esiste almeno un insieme di questo tipo con cardinalità maggiore di $ k $ e quindi, per il lemma 1, avremo $ f(k)=1 $, che è assurdo.

Punto 2

Affermo che esiste sempre almeno una funzione che rispetta l'ipotesi tale che
$ f(k)=n $ per $nin{1,2,...,k+1} $, per esempio si può costruire in questo modo:

$ f(x)={ ( 1 if xk):} $, per $ n le k $

$ f(x)={ ( 1 if xk and xne2^alphak and alpha in NN+{0}):} $, per $ n =k +1 $

Punto 3

Calcolo \[ \sum_{n \in V(k)} n \]

Per i punti 1 e 2 posso scrivere:

$ sum_ {n \in V(k)}n=sum_(n=1)^(k+1)n=((k+1)(k+2))/2 $

CVD

sperando di non aver fatto errori stupidi questa volta.

[Studente Anonimo]

Penso sia corretto!

Posto una dimostrazione alternativa, l'idea fondamentalmente è la medesima alla tua, ma è in modo diretto e non per assurdo

Dimostrazione che \( f(n) \leq n+1 \)

Se \( n > m \) abbiamo allora che
\[ f(n) = f(m + (n-m)) \geq f(m) + f( f(n-m)) -1 \geq f(m) \]
Dunque \(f\) è non decrescente. Chiaramente \(f= 1 \) è una soluzione, supponendo \(f \neq 1 \) allora scegliamo \( x \in \mathbb{N} \) minimale tale che \( f(x) > 1 \). Allora abbiamo che \( f(y) \geq f(x) > 1 \) per ogni \( y \geq x \). Supponiamo dunque \( f(n) > n \) per qualche \(n \in \mathbb{N} \). Abbiamo che
\[ f(f(n)) = f( ( f(n)-n) + n ) \geq f( f(n)-n) + f(f(n)) -1 \]
pertanto \( f( f(n)-n) \leq 1 \) e quindi \( f( f(n)-n) = 1 \) dunque \( f(n)-n < x \). Esiste allora un valore massimale per \( f(n)-n \). Diciamo che con \( \ell \in \mathbb{N} \) otteniamo questo valore massimale \(M\), dunque \( f(\ell)- \ell = M \geq 1\). Per monotonia e per l'ipotesi che deve soddisfare la funzione abbiamo dunque
\[ 2\ell + M \geq f(2\ell) = f(\ell + \ell) \geq f(\ell ) + f( f(\ell)) - 1 \geq f(\ell) + f(\ell) -1 \]
\[ 2 \ell + M \geq 2(\ell + M) - 1 \]
dunque \( M \leq 1 \) e pertanto \( f(k) \leq k+1 \) per ogni \(k \in \mathbb{N} \).

Una possibile famiglia, diversa da quella che hai presentato te, di funzioni per \( 1 \leq n \leq k \), è la seguente
\[ f_n(x) = \max \{ x + n - k , 1 \} \]
Mentre
\[ f_{k+1} (x) = \left\{\begin{matrix}
x& k \not\mid x \\
x+1 & k \mid x
\end{matrix}\right. \]