OliForum Matematico

tutte le $ ~ f: \mathbb{N} \rightarrow \mathbb{N} $ tali che $ ~ f(f(n)) < f(n+1) $

Premetto che è la prima volta che risolvo questo tipo di problema quindi potrei dirle grosse: $ f(n)=1 $ implica $ f(f(n-1))<1 $ ma questo contrasta l'ipotesi e ci porta all'unico caso $ n=1 $.Ponendo,induzione, che questo valga per i primi n naturali ovvero $ f(n)=n $ si arriva a fare per n+1 il medesmo ragionamento fatto su 1 (in effetti il passo base ha fatto sì che n+1 sia equivalente a 1 per la dimostrazione ): $ f(k)=n+1 $ implica $ f(f(k-1))< n+1 $ ma per salvaguardare la biettività si ha la sola opzione $ k-1=n $ che implica $ k=n+1 $ ovvero che la funzione è necessariamente d'identità. è giusta o no?
p.s:per chi non l'avesse mai vista ho usato un'induzione "rinforzata" che però è equivalente a quella tradizionale
ehm solo ora mi viene un dubbio,ma per come è scritta da edriv significa che è biettiva no?non vorrei aver fatto il solito errore grossolano..
altra domanda(vi è una differenza di tempo tra i 3 p.s) :se è vera la dimostrazione mi sembra sia ininfluente il numero di f messi davanti a n nella seconda ipotesi da edriv,purchè esso(il numero di f) sia maggiore di 0 la conclusione non cambia...sempre se è giusta la mia prova..

comunque anche se l'ipotesi non dicesse se la funzione è biunivoca o meno non dovrebbe cambiare la cosa a ben pensarci:pechè se nell'ipotesi induttiva poniamo che oltre al fatto che $ f(n)=n $ anche che non esiste altro k diverso da n tale che $ f(k)=n $ abbiamo nel passo conseguente che $ f(n+1)=n+1 $ e che non esiste altro k diverso da n+1 tale che $ f(k)=n+1 $ e dunque abbiamo la cosa che io più pigramente avevo presupposto vera..
è molto tardi quindi mi affido alla speranza circa quanto ho detto..
notte
p.s:questo però presuppone la suriettività..che mi sembra sia detta dall'ipotesi o no?

Carlein ha scritto: $ f(n)=1 $ implica $ f(f(n-1))<1 $ ma questo contrasta l'ipotesi e ci porta all'unico caso $ n=1 $.

l'idea è buona, però pensa, la funzione è da N in N ma chi ti assicura che nel codominio della funzione ci sia 1?poni invece ke esiste (deve esistere giusto? ) n t.c. f(n) è minimo..

Carlein ha scritto:se è vera la dimostrazione mi sembra sia ininfluente il numero di f messi davanti a n nella seconda ipotesi da edriv,purchè esso(il numero di f) sia maggiore di 0 la conclusione non cambia...sempre se è giusta la mia prova..

ehm, se hai solo f(n)<f(n+1) non va bene anche 3^n?

jordan ha scritto:

Carlein ha scritto:

Carlein ha scritto:se è vera la dimostrazione mi sembra sia ininfluente il numero di f messi davanti a n nella seconda ipotesi da edriv,purchè esso(il numero di f) sia maggiore di 0 la conclusione non cambia...sempre se è giusta la mia prova..

ehm, se hai solo f(n)<f(n+1) non va bene anche 3^n?

si si:infatti come un demente avevo postulato in generale la surriettività(che infatti in tal caso 3n non soddisferebbe)...speriamo la notte sia consigliera..

Forse jordan è stato più consigliero della notte
notte..di quel che rimane

tex impazzisce di notte?:la riscrivo
Essendo definita su N la f ammette sicuramente minimo :$ f(f(n-1))<f(n) $ per definizione di minimo n-1 non può appartenere a N e dunque n=1.Il minimo è f(1). Ora chiediamoci qual'è il minimo valore maggiore di f(1):di nuovo $ f(f(n-1)<f(n) $ quindi per definizione di n: $ n-1=1 $ ovvero il nuovo minimo è $ f(2) $:procedendo così indefinitamente anzi induttivamente si ha che la funzione è strettamente crescente! Affianchiamo l'ipotesi a questo: $ f(f(n-1))<f(n) $ e $ f(n-1)<f(n) $ ora per la prima formula f(n-1)<n>n.Se $ f(n-1)< (n-1) $ si avrebbe per la stretta crescenza $ f(n-2)<n-2 $ e $ f(n-3)<n-3 $ ...fino a $ f(1)<1 $ che è impossibile. Dunque $ f(n-1)=(n-1) $ ovvero la funzione è identità.
Ora mi pare più sensatata...
p.s:forse impazzisce pure di giorno perchè mi scrive ostinatamente f(n-1)<n>n quando io voglio scrivere solo f(n-1)<n

IMO 1977, problema 6.

sapevo la fonte, infatti è ben noto..ah, carlein, io ci ho messo molto a impararlo, ma $ 0 \in N $

Volevo fare delle appendici:prima veramente banale:come già accennato prima e corretto da jordan,il numero di f davanti ad n-1 non fa differenza nelle conclusioni purchè maggiore di 1(poichè non è ipotizzato f surriettivo).Secondo fattarello:variando il problema nella maniera più banale di questo mondo:mi sono chiesto che succede se invece di n-1 considero n-c.Con c generico naturale assegnato?Diciamo che il tipo di dimostrazione è analogo ma la funzione che ne esce fuori è un pò più carina dell'altra: scomponiamo i naturali nei sottoinsiemi "consecutivi" di numeri che hanno i residui modulo c da 1 a c(ovvero 0).Ora scomponiamo la funzione f nel caso in cui il dominio di ciascuna è l'insieme dei naturali aventi lo stesso residuo con c.Ora il ragionamento per ciascuna funzione è analogo a quello che precedentemente fatto per 1:difatti prima pure abbiamo considerato i numeri aventi residuo uguale modulo 1;ovvero i naturali!! Però abbiamo un risultato un pò più generico difatti ripetendo quel ragionamento si ha che è sufficente e necessario che f(n) appartenga allo stesso sottoinsieme a cui appartiene n.Dunque i possibili codomini sono dati dall'unione di tutte le c-uple ordinate di quei sottoinsiemi suddetti in cui è possibile la ripetizione di ciascun elemento del sottoinsieme:ad esempio per c=3 il sottoinsieme (1,2,3) genera $ 3^3 $ codomini:ripeto nel caso di 1 si ha il sottoinsieme (n), per ogni n,la cui upla è appunto (n):la funzione identità!!
se è una banalità perdonatemi...ma essendo la prima volta che vedo ste cose mi entusiasmo..

jordan ha scritto:sapevo la fonte, infatti è ben noto..ah, carlein, io ci ho messo molto a impararlo, ma $ 0 \in N $

ah si? buono a sapersi;vabbè comunque sposterebbe gli assurdi su -1 che dovrebbe non appartenere a N ..no?
Curiosità futile:ma di solito non si dice $ N_0 $ per indicare questo?

Tibor Gallai ha scritto:IMO 1977, problema 6.

Già già... bravo Carlein!!

Oooopsss
Scusate stamani facendo i conti con i fanatsmi del passato mi sono ricordato lo stupido tentativo di "generalizzare" le condizioni del problema, mettendo f(f(n-c))<f(n);ebbene quando parlo delle delle u-ple e la definisco come una condizione necessaria oltre che sufficente.Ebbene non è così ,la condizione è solo sufficente perchè come al solito non mi sono perito di andare a controllare efficentemente che la mia ipotesi fosse vera ma me ne sono "persuaso" soprattutto che dal fatto che quella spiegazione prendeva come caso particolare il problema di edriv(troppo bello per essere falso).Provandolo su di un esempio si vede bene che tale condizione è solo sufficente ma per niente necessaria....non so se con quelle condizioni si può pervenire ad una distribuzione prevedibile come le identità e le u-ple,ovvero non so se si può effettivamente trovare una classe a cui appartengano tutti i codomini,con una formula semplice,anche se però mi sembra di capire che si possono porre delle condizioni "proibitive" alla funzione....se a qualcuno interessa sono grato se mi dice che ne pensa altrimenti fa niente...
Scusate la mia ciucciagine e la proporzionale superficialità nel controllare quello che dico...