[L04] Doppia funzione! (SNS 2016-1)

[mr96]

Sia [tex]g(n)[/tex] la parte intera di [tex]\sqrt{n}[/tex] con [tex]n \in \mathbb{N}[/tex] e sia [tex]f : \mathbb{N} \rightarrow \mathbb{N}[/tex] una funzione iniettiva tale che $f(2016)=1916$. Mostrare che esiste $n \in \mathbb{N}$ tale che $g(f(n))>g(n)$.

[matematto]

Testo nascosto:

Lemma 1
Sia $m\in\mathbb{N}$, allora gli $j\in\mathbb{N}$ tali che $g(j)\le m$ sono esattamente $(m+1)^2$, perchè sono tutti gli interi da $0$ a $(m+1)^2-1$.

Dimostrazione
Consideriamo adesso l'insieme $\mathbb{A}=\{0, 1, 2, ... , 1935\}$. Tutti i suoi $1936=44^2$ elementi godono della proprietà di avere $g(k)<44$ $ $ $\forall k\in\mathbb{A}$
Supponiamo per assurdo che $\forall k\in\mathbb{A}$ si ha che $g(f(k))<g(k)\le 43$. Per il Lemma 1 gli interi la cui parte intera della radice è $\leq 43$ sono esattamente i primi $44^2=1936$ interi, tutti e soli gli elementi di $\mathbb{A}$. Ciò significa che $\forall k\in\mathbb{A}$ si ha che $f(k)\in\mathbb{A}$. Questo è assurdo perchè per ipotesi $f(n)$ è una funzione iniettiva e $f(2016)=1916\in\mathbb{A}$, quindi, per Pigeonhole, esisterà $a\in\mathbb{A}$ tale che $f(a)\not\in\mathbb{A}\rightarrow f(a)>1935 \rightarrow g(f(a)) \geq 44>g(a)$.
C.V.D.

[Rho33]

Cosa molto divertente ed inutile ( ): la mia soluzione è quasi identica a quella di matematto , soltanto che fino a poco fa avevo letto $f(2026)=1926$ che d'altronde funziona per un pelo, perché $45^2=2025$ e quindi tutto il discorso si può rifare identico! Secondo me sarebbe stato più carino mettere il $2026$, tanto per farla proprio strettissima

[polarized]

Riguardo la "ristrettezza" della tua osservazione: non bastava forse che $$f(2026)<2025$$?

[Rho33]

Uh certo, ovviamente! Il mio "funziona per un pelo" si riferiva al caso in cui devono sempre differire di $100$, comunque certo, il limite massimo è quello che dici tu!

[Enigmatico]

Soluzione alternativa:

$f$ è iniettiva, pertanto è monotona.
- $f$ strettamente crescente.
Si ha $f(h)<2016 \forall h<2016,h\in N$.
Ora, $f:N\rightarrow N$ pertanto h può assumere $2016$ valori distinti, mentre $f(h)$ solo $1916$. Segue, per pigeonhole, che esistono $0\leq h_{1},h_{2}\leq 2015$ tali che $f(h_{1})=f(h_{2})$.
Ciò è assurdo per l'iniettività di $f$.
- $f$ strettamente decrescente.
$f(h)>1916\forall 0\leq h\leq 2015,h\in N$.
in particolare $f(0)>1916$.
Si calcolino $g(f(0))$ e $g(0)$:
$g(f(0))>\left \lfloor{\sqrt{1916}}\right \rfloor>0$ mentre $g(0)=0$.
Segue la tesi.

[polarized]

Soluzione alternativa:

$f$ è iniettiva, pertanto è monotona.
[...]

Non vorrei dire una cavolata, ma per poter dire questo dovresti avere come minimo qualche condizione sulla derivabilità, che non ho idea di cosa voglia dire se la funzione si definisce nei naturali

Ti faccio un esempio di una funzione iniettiva e non monotona:

$$
f(n) = \begin{cases}2 & n=1\\
1 & n = 2\\n & n\ge 3\end{cases}
$$

[Enigmatico]

Hai ragione, ho dimenticato la continuità

[Rho33]

Io sono molto d'accordo con polarized, pur sapendone pochissimo. Tempo mi ero posto lo stesso dubbio e poi ho iniziato a trovare controesempi a manetta In particolare credo basti la continuità (ma non ne sono sicurissimo).

Tanto per mettere un altro controesempio (iniettiva ma non monotona ovviamente):

$$f: \mathbb{R} \mapsto \mathbb{R}: f(x)= \dfrac {1}{x} \ \ \text{per} \ \ x \neq 0 \ \ \text{e} \ \ f(x)=0 \ \ \text{per} \ \ x=0 $$

[polarized]

Io sono molto d'accordo con polarized, pur sapendone pochissimo. Tempo mi ero posto lo stesso dubbio e poi ho iniziato a trovare controesempi a manetta In particolare credo basti la continuità (ma non ne sono sicurissimo).

Tanto per mettere un altro controesempio (iniettiva ma non monotona ovviamente):

$$f: \mathbb{R} \mapsto \mathbb{R}: f(x)= \dfrac {1}{x} \ \ \text{per} \ \ x \neq 0 \ \ \text{e} \ \ f(x)=0 \ \ \text{per} \ \ x=0 $$

Chiaramente l'esempio va bene. Per il resto, cosa significa la continuità in una funzione definita nei naturali? Se invece si parla dei reali, la continuità basta solo per la monotonia in senso lato (credo) e non quella in senso stretto utilizzata da Enigmatico (in formule, l'iniettività mi consente di dire, prendendo per esempio la crescenza, $f'(x)\ge 0$ e non $f'(x)>0$)