funzionale che non deve funzionare
funzionale che non deve funzionare
A mio parere è davvero carino:
Dimostrare che non può esistere nessuna funzione f da N a N tale che $ f(f(n))=1987+n $ Spero che non sia mai stato postato di recente(magari da salva )...nel caso se mi avvertite per mp così lo cancello, vi sono grato
Dimostrare che non può esistere nessuna funzione f da N a N tale che $ f(f(n))=1987+n $ Spero che non sia mai stato postato di recente(magari da salva )...nel caso se mi avvertite per mp così lo cancello, vi sono grato
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Premesso che ho iniziato a vedere (e non a fare) funzionali a Cesenatico quest'anno provo a mettere una "soluzione"
Supponiamo che $ f(n) \leq n $: allora avremmo $ f(f(n)) \leq f(n) \leq n $ ma siccome $ f(f(n))=n+1987 $ abbiamo l'assurdo.
Quindi abbiamo $ f(n) > n $. Se $ f(n) $ non fosse una funzione lineare da N in N allora non lo sarebbe nemmeno $ f(f(n)) $ (per funzione lineare intendo della forma $ f(n)=kn+l $) Ora vediamo che $ f(f(n))=n+1987 $ implica che $ k $ dev'essere uguale a 1 (questo perchè 1 è elemento neutro della moltiplicazione, andrà bene detto così?)
Quindi possiamo scrivere $ f(n)=n+h $ con $ h \in \mathbb N $
Ma allora $ f(f(n))=n+1987 \Rightarrow f(n+h)=n+1987 \Rightarrow n+2h=n+1987 $ che ovviamente è impossibile per $ h \in \mathbb N $
Per prima cosa volevo chiedere se è giusta, in tal caso se è abbastanza dire
Se $ f(n) $ non fosse una funzione lineare da N in N allora non lo sarebbe nemmeno $ f(f(n)) $
oppure c'è da dimostrare qualcosa di più e infine ogni consiglio è gradito (anche per la forma).
Ciao
Supponiamo che $ f(n) \leq n $: allora avremmo $ f(f(n)) \leq f(n) \leq n $ ma siccome $ f(f(n))=n+1987 $ abbiamo l'assurdo.
Quindi abbiamo $ f(n) > n $. Se $ f(n) $ non fosse una funzione lineare da N in N allora non lo sarebbe nemmeno $ f(f(n)) $ (per funzione lineare intendo della forma $ f(n)=kn+l $) Ora vediamo che $ f(f(n))=n+1987 $ implica che $ k $ dev'essere uguale a 1 (questo perchè 1 è elemento neutro della moltiplicazione, andrà bene detto così?)
Quindi possiamo scrivere $ f(n)=n+h $ con $ h \in \mathbb N $
Ma allora $ f(f(n))=n+1987 \Rightarrow f(n+h)=n+1987 \Rightarrow n+2h=n+1987 $ che ovviamente è impossibile per $ h \in \mathbb N $
Per prima cosa volevo chiedere se è giusta, in tal caso se è abbastanza dire
Se $ f(n) $ non fosse una funzione lineare da N in N allora non lo sarebbe nemmeno $ f(f(n)) $
oppure c'è da dimostrare qualcosa di più e infine ogni consiglio è gradito (anche per la forma).
Ciao
Ho una serie di obiezioni da muovere: al primo punto tu dici che se f(n)<n allora f(f(n))<f(n), ma questo è vero solo se supponi f(n)<n per ogni n;va da sè che così imponi una restrizione:difatti ciò potrebbe andare per alcuni n e per altri no, e se nn consideri questo non stai parlando veramente in generale.Poi tu dai questo lemma generale:se f(f(n)) è lineare allora f(n) è lineare:considera la funzione che traspone l'1 nel 2 e il 2 nell 1 e così per tutte le coppie successive,il 3 nel 4 e il 4 nel 3 tipo...bene f(f(n))=n ovvero una funzione lineare, ma nn lo è f(n).Può darsi che io non abbia capito bene quello che volevi dire in tal caso scusami....
Notte
Notte
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
Mi e' venuta in mente questa funzione carogna
$ $f(x)=\left\{\begin{array}{ll}x|a & \frac{a}{x}\\ \\ x\nmid a & x\end{array}\right. $ $
$ $f(x)=\left\{\begin{array}{ll}x|a & \frac{a}{x}\\ \\ x\nmid a & x\end{array}\right. $ $
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
avevo prima postato $ $\frac{a}{x}$ $, ma mi ero accorto che non era proprio dai naturali ai naturali, ma sono dai divisori di a ai divisori di a. Ergo, servendomi una funzione che composta con se stessa mi desse l'identita', l'ho "patchata" con l'identita'.
eli9o: attento che la negazione di $ $f(n)\leq n \quad\forall n\in \mathbb{N}$ $ non e' $ $f(n)> n \quad\forall n\in \mathbb{N}$ $, ma $ $\exists n\in \mathbb{N}: f(n)>n$ $
il fatto che la f non puo' stare sempre sotto l'identita', non vuol dire che deve stare sempre sopra.
edit: altra funzioncina carina che non e' proprio lineare ma composta con se da l'identita' (dovrebbe essere la formula generale di quella detta da Carlein)
$ $f(x)=x+a-2(x\mod a)$ $
con $ $x\mod a$ $ la funzione resto
eli9o: attento che la negazione di $ $f(n)\leq n \quad\forall n\in \mathbb{N}$ $ non e' $ $f(n)> n \quad\forall n\in \mathbb{N}$ $, ma $ $\exists n\in \mathbb{N}: f(n)>n$ $
il fatto che la f non puo' stare sempre sotto l'identita', non vuol dire che deve stare sempre sopra.
edit: altra funzioncina carina che non e' proprio lineare ma composta con se da l'identita' (dovrebbe essere la formula generale di quella detta da Carlein)
$ $f(x)=x+a-2(x\mod a)$ $
con $ $x\mod a$ $ la funzione resto
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Grazie per le correzioni, alla fine si impara sempre così...
Per la storia della funzione lineare avete perfettamente ragione, adesso vedo di pensarci un po' di più...
@ Carlein: non ti preoccupare, hai capito benissimo!
Sì, è vero... Ma diciamo che se non fossi così masochista avrei preso $ h\in \mathbb Z $ e non ci sarebbe stato bisogno di tutto ciò.eli9o: attento che la negazione di $ f(n)\leq n \quad\forall n\in \mathbb{N} $ non e' $ f(n)> n \quad\forall n\in \mathbb{N} $, ma $ \exists n\in \mathbb{N}: f(n)>n $
Per la storia della funzione lineare avete perfettamente ragione, adesso vedo di pensarci un po' di più...
@ Carlein: non ti preoccupare, hai capito benissimo!
Re: funzionale che non deve funzionare
Lo volevo postare giusto due giorni fa per vedere se saltava fuori una soluzione meno indecente della miaCarlein ha scritto: Spero che non sia mai stato postato di recente(magari da salva )
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Innanzitutto, dato un $ s $ naturale, definisco $ f_{s}(n)=f(f(...(f(n))...) $, con $ s $ segni $ 'f' $ ripetuti.
Dimostriamo che se $ j $ e $ k $ sono dei naturali tali che $ j\neq k $ (poniamo $ j<k $), allora $ f_{j}(n)\neq f_{k}(n) $. Se infatti fosse $ f_{j}(n)=f_{k}(n) $, la $ f_{s}(n) $ (con $ n $ fissato e $ s $ variabile) diventerebbe, per $ s\geq j $, periodica di periodo $ k-j $, assumendo solo un numero finito di valori. Dalla definizione però sappiamo che $ f_{2s}(n)=1987\cdot s+n $, dunque non esiste un massimo e i valori assunti dalla funzione sono infiniti.
Manipolando la definizione abbiamo che $ f_{3}(n)=f(f(f(n)))=f(1987+n)=1987+f(n) $, dunque $ f(1987+n)-f(n)=1987 $. Ciò significa che se $ m\equiv n\ mod\;1987 $, allora $ f(m)\equiv f(n)\ mod\;1987 $.
Supponiamo ora che sia $ f(n)=a $. Se $ a\equiv n\ mod\:1987 $ e $ a\geq n $, abbiamo che $ a = 1987\cdot t +n $, con $ t $ naturale. Avremmo però che $ f_{2t}(n)=f_{1}(n)=1987\cdot t +n $, il che è impossibile per quello che abbiamo dimostrato in precedenza. In modo simile si esclude anche il caso $ n\geq a $. Dunque $ a $ appartiene a una diversa classe di congruenza modulo $ 1987 $ rispetto a $ n $.
Consideriamo la relazione che associa alla classe di congruenza modulo $ 1987 $ di $ n $ quella di $ f(n) $. Poichè $ f(f(n))=1987+n\equiv n\ mod\;1987 $ e la classe di $ f(n) $ è distinta da quella di $ n $, possiamo suddividere le classi di congruenza modulo $ 1987 $ in gruppi da due elementi, ma questo è assurdo in quanto le classi di congruenza sono $ 1987 $, e $ 1987 $ non è divisibile per $ 2 $.
La dimostrazione rimane valida se al posto di $ 1987 $ mettiamo un qualunque altro numero dispari; se invece avessimo un numero pari (chiamiamolo $ 2l $), un controesempio è dato da $ f(n)=n+l $.
Dimostriamo che se $ j $ e $ k $ sono dei naturali tali che $ j\neq k $ (poniamo $ j<k $), allora $ f_{j}(n)\neq f_{k}(n) $. Se infatti fosse $ f_{j}(n)=f_{k}(n) $, la $ f_{s}(n) $ (con $ n $ fissato e $ s $ variabile) diventerebbe, per $ s\geq j $, periodica di periodo $ k-j $, assumendo solo un numero finito di valori. Dalla definizione però sappiamo che $ f_{2s}(n)=1987\cdot s+n $, dunque non esiste un massimo e i valori assunti dalla funzione sono infiniti.
Manipolando la definizione abbiamo che $ f_{3}(n)=f(f(f(n)))=f(1987+n)=1987+f(n) $, dunque $ f(1987+n)-f(n)=1987 $. Ciò significa che se $ m\equiv n\ mod\;1987 $, allora $ f(m)\equiv f(n)\ mod\;1987 $.
Supponiamo ora che sia $ f(n)=a $. Se $ a\equiv n\ mod\:1987 $ e $ a\geq n $, abbiamo che $ a = 1987\cdot t +n $, con $ t $ naturale. Avremmo però che $ f_{2t}(n)=f_{1}(n)=1987\cdot t +n $, il che è impossibile per quello che abbiamo dimostrato in precedenza. In modo simile si esclude anche il caso $ n\geq a $. Dunque $ a $ appartiene a una diversa classe di congruenza modulo $ 1987 $ rispetto a $ n $.
Consideriamo la relazione che associa alla classe di congruenza modulo $ 1987 $ di $ n $ quella di $ f(n) $. Poichè $ f(f(n))=1987+n\equiv n\ mod\;1987 $ e la classe di $ f(n) $ è distinta da quella di $ n $, possiamo suddividere le classi di congruenza modulo $ 1987 $ in gruppi da due elementi, ma questo è assurdo in quanto le classi di congruenza sono $ 1987 $, e $ 1987 $ non è divisibile per $ 2 $.
La dimostrazione rimane valida se al posto di $ 1987 $ mettiamo un qualunque altro numero dispari; se invece avessimo un numero pari (chiamiamolo $ 2l $), un controesempio è dato da $ f(n)=n+l $.