funzionale che non deve funzionare

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

funzionale che non deve funzionare

Messaggio da Carlein » 30 lug 2008, 22:14

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 :lol: )...nel caso se mi avvertite per mp così lo cancello, vi sono grato :wink:
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"

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 30 lug 2008, 23:55

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

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 31 lug 2008, 00:48

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
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"

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 31 lug 2008, 00:54

Mi e' venuta in mente questa funzione carogna :twisted:
$ $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

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 31 lug 2008, 01:11

Che controesempio buffo! :D
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"

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 31 lug 2008, 01:26

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'. :D

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

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 31 lug 2008, 08:51

Grazie per le correzioni, alla fine si impara sempre così...
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 $
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ò.

Per la storia della funzione lineare avete perfettamente ragione, adesso vedo di pensarci un po' di più...

@ Carlein: non ti preoccupare, hai capito benissimo!

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Re: funzionale che non deve funzionare

Messaggio da salva90 » 31 lug 2008, 09:57

Carlein ha scritto: Spero che non sia mai stato postato di recente(magari da salva :lol: )
Lo volevo postare giusto due giorni fa per vedere se saltava fuori una soluzione meno indecente della mia :roll:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

nicelbole
Messaggi: 14
Iscritto il: 16 mag 2007, 16:47

Messaggio da nicelbole » 31 lug 2008, 14:50

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 $.

Carlein
Messaggi: 315
Iscritto il: 26 nov 2007, 18:16
Località: Napoli

Messaggio da Carlein » 31 lug 2008, 16:08

Già! :D
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"

Rispondi