Ajde za početak da odradimo neparni slučaj

Ako je za neko celo , onda funkciju definišemo kao . Jasno je da je .

Što se tiče parnog slučaja za sad samo
, gde je proizvoljan ali fiksiran prirodan broj.

Dobro je , s tim što za možemo da dopustimo i (u kom slučaju je rešenje ).

Novi napredak:

Zadatak će biti rešen ukoliko pokažemo da brojevi iz skupa daju parno mnogo ostataka pri deljenju sa .

Još veći napredak - konačno sam rešio zadatak! Mislim da je ovo definitivno zadatak koji me je najviše izmučio ikada, ali sad mu je došao kraj.

Nadam se da se niko neće ljutiti što odmah objavljujem rešenje umesto da još malo sačekam, ali ipak, možda je neko već i probao da ga uradi pa nije uspeo, ko hoće još malo da se muči sam neka još ne čita ovo što ću napisati, a ja sam nestrpljiv da podelim ovo, po mom (neskromnom) mišljenju, zaista sjajno rešenje. Samo da napomenem da ćete verovatno videti nebulozne tehnike koje nijedna normalna osoba ne koristi prilikom rešavanja funkcionalnih jednačina, ali eto ja ih koristio :) Dakle, svi vi koji hoćete još malo da pokušavate sami ovo je pravi momenat da prestanete sa čitanjem, svi ostali nastavite :)

Najpre navodim rezultat:

Data funkcionalna jednačina ima rešenja za i samo za neparne i za .

Rešenje ide u 3 dela.

1) Neparno ili .

Kolega uranium je ovo već napisao, ali ponoviću kompletnosti radi. U ovom slučaju funkcionalna jednačina ima jedno rešenje za neparno , odnosno ( je proizvoljna konstanta) za .

2)

Malo ću izmeniti oznake radi lakšeg snalaženja. Dokazaću sledeće:

Ne postoji funkcija za koju važi:




gde je unapred zadati prirodan broj.

Dokaz:

Najpre indukcijom po dokazujemo sledeće tvrđenje:



Pretpostavimo da postoji broj takav da je . Uvrštavajući u relaciju imamo:



pa dobijamo kontradikciju. Dakle, tvrđenje zaista važi za . Pretpostavimo da važi za sve brojeve manje od i dokazujemo istinitost za . Opet pretpostavimo da postoji za koje važi . Uvrštavajući u imamo:



Primetimo da ako onda mora biti i , jer je (na osnovu indukcijskih hipoteza). Kako je , to je i , pa je i . Time smo dobili kontradikciju, pa je dokaz tvrđenja završen. Primetimo da štaviše važi stroga nejednakost, i da ovo tvrđenje neposredno implicira da je rastuća.

Neka je niz dat rekurentnom formulom , . Dokazaćemo indukcijom po da za sve i sve važi sledeće tvrđenje (koje neposredno implicira da takva funkcija ne postoji):



Uvrštavajući u jednakost imamo , pa mora biti , a pošto je funkcija rastuća za sve važi . Pretpostavimo da važi za . Za bilo koje iz imamo:




3) Parno

Evo ga ono baksuzno :)

Neka je . Tada je i , odnosno iz čega dobijamo i , pa iteracijom zaključujemo da važi i za sve . Imamo dve mogućnosti: ili je periodična (počevši od neke tačke) ako je ili je injektivna.

Pretpostavimo da je periodična. Tada uzima konačan skup vrednosti. Neka je najveća od njih. Ukoliko je uvrštavanjem u datu funkcionalnu jednačinu dobijamo da je , kontradikcija. Dakle, je jedina najveća slika. Neka je druga po veličini (ne mora biti jedinstvena). Iz polazne jednačine dobijamo (u suprotnom ne bi bila druga po veličini), pa pošto je jedinstvena sledi da postoji broj (konkretno je u pitanju) koji se slika u . Takođe primetimo da se prva dva po veličini elementa razlikuju baš za , a slično, ako je treći po veličini onda važi pa je i razlika drugog i trećeg po veličini upravo , i tako sve do kraja. Dakle, skup vrednosti posmatrane funkcije je skup , gde je neki prirodan broj, i pri tome je . Neka je period funkcije.

Pretpostavimo da se samo nalazi van periodičnog dela. Tada je . Dalje, imamo da važi:



S druge strane, takođe važi . Iz ovog i prethodnog sledi da je , odnosno je fiksna tačka ove funkcije. Pokušajmo da nađemo prvu iteraciju koja je fiksna tačka. Primetimo da je nemoguće , kao i (ovo drugo sledi iz jedinstvenosti ), pa nam preostaje ili . U oba slučaja dolazimo do situacije da je za neke različite . To dalje znači , odnosno . Kako je , preostaje nam jedino da je . Međutim, to znači . Dakle, svi ovi brojevi se preslikavaju u istu sliku, recimo . Ne može biti jer bi tada bilo . Važi za sve . Ako je onda imamo , odnosno , dok za odmah važi , pa i . Međutim, to dalje znači da za proizvoljne različite imamo , pa i . Kontradikcija.

Dakle, bar još se ne ubraja u periodičnost, odnosno vrednost je jedinstvena. Neka je . Ako je onda iz jedinstvenosti i činjenice da je imamo da je . Za uzmimo takvo da je . Stavljajući u početnu funkcionalnu jednačinu, dobijamo da je , pa opet iz jedinstvenosti imamo da je . U oba slučaja smo dobili kontradikciju, jer, kako je ranije pokazano, broj ne pripada skupu vrednosti posmatrane funkcije.

Time je dokazano da je injekcija.

Neka je, dalje, , , i . Ovi skupovi su međusobno disjunktni, a pošto je injekcija, važi . Očigledno je i . Pošto je , imamo da je . Primetimo još i da iz date funkcionalne jednačine sledi .

Za definišimo . Označimo još i . Može se dogoditi i da neko ne postoji, i u tom slučaju ga jednostavno nadalje ignorišemo. Tvrdimo da je . Za početak, očigledno je da za sve . S druge strane, ako bi za neko važilo , onda bismo imali , što je u kontradikciji sa minimalnošću . Proverimo sada da li neki element različit od svih pripada posmatranoj uniji. Predstavimo ga u obliku ukoliko je to moguće, odnosno ako to nije moguće u obliku za neko , gde . Tada važi , pa sledi , odnosno .

Dakle, ima konačno mnogo elemenata, pa to važi i za , odnosno svi sem konačno mnogo prirodnih brojeva su sadržani u skupu slika funkcije . Zaključujemo da svi postoje, pa ima baš elemenata. Međutim, kako su i disjunktni i sa istim brojem elemenata, njihova unija mora sadržati paran broj elemenata, dok je neparno. Kontradikcija!

---

Moj duboki naklon i beskonačno divljenje svima koji su uspeli da ovo pročitaju do kraja :) Ako neko uspe da nađe jednostavnije rešenje od ovog ili bar da uprosti neki korak rešenju neka se ne ustručava da to ovde napiše, ja eto nisam uspeo. Naravno, kao i uvek ću rado otkloniti bilo kakve eventualne nejasnoće u vezi sa ovim mojim rešenjem.

Eh, konacno da dam komentar na ovo resenje. Nekoliko puta sam krenuo da citam ali posto je dosta obimno onda sam uvek odlagao za neki drugi put iako si pretpostavljam bio nestrpljiv da cujes komentare :-) Sada sam konacno resio da ga pazljivo procitam ali nisam skroz zavrsio jer sam na sredini naleteo na problem:


Ne razumem ovaj dokaz. Mislim da si dokazao samo da ako za neko n vazi onda vazi .

Ako smatras da nije tako onda ovaj dokaz vazi i za k=-1 (svi uslovi dokaza su zadovoljeni) ali za k=-1 ipak postoji resenje odnosno za k=1 u izmenjenom obliku zadatka:

_{[Ovu poruku je menjao srki dana 23.03.2006. u 11:44 GMT+1]}

Meni se čini da je dokazano , ali samo za - što onda nije dovoljno da odmah obori postojanje f-je. Jer ja sam onaj argument shvatio ovako: fiksiramo a pustimo da raste - pa pošto je neograničen niz dobijemo kontradikciju. Tako da za sad mislim da to neće proći.

Ako je ili onda važi za svako ali to ne izaziva kontradikciju.

_{[Ovu poruku je menjao uranium dana 23.03.2006. u 11:03 GMT+1]}

Iskreno, jesam bio malo nestrpljiv, uvek volim da pročitam komentare (bilo pozitivne ili negativne) na neko moje rešenje (naravno, niko nije obavezan da odgovara, svako ima izbor šta će da čita a šta neće), ali ako si ciljao na ono što sam posle nekoliko dana obrisao svoju poruku pa je ponovo poslao to je stvarno bilo slučajno, hteo sam da ispravim sitnu grešku u kucanju pa sam greškom obrisao celu poruku.

Uranium je dobro shvatio glavnu ideju te indukcije: pošto je niz neograničen, ako pokažemo da navedena nejednakost važi za svako odmah ulećemo u kontradikciju.

Razumem šta mi tačno zamerate, ali ponovo sam prekontrolisao taj deo rešenja i mislim da je ipak korektno. Naime:

U svakoj indukcijskoj iteraciji kreće od , dakle su sve vrednosti od pa naviše. Uprkos tome mogu da primenim indukcijski korak jer imam tri ugneždene funkcije, na onu skroz unutra (gorecitirano parče) ne primenjujem indukcijski korak već samo koristim da je za sve , a preostala dva puta argumenti su odnosno koja su oba veća ili jednaka . To je ujedno i mesto gde primenjujem ograničenje za i na tom mestu dokaz pada za (odnosno za pri izmenjenim oznakama).

Naravno, ako i dalje nije jasno slobodno se javite pa ćemo još prodiskutovati.

Hvala Bojane, sad je sve jasno

Nekako sam se bio istripovao da je u formulama i jedno te isto

Ma ne, nije mi to palo na pamet, rekao sam to jer si se zaista potrudio da napises resenje i logicno je da ocekujes povratnu informaciju (svako bi to ocekivao). Nadam se da me nisi pogresno shvatio, izvinjavam se zbog offtopic-a.


To je to! Svaka cast na resenju! Nije bilo tesko dokazati da je funkcija injekcija ali sam se posle zaglavio i nije bilo sanse da mrdnem :-)

_{[Ovu poruku je menjao srki dana 24.03.2006. u 07:20 GMT+1]}

Ma nema problema, meni prvom je malo glupo izgledalo što posle nekoliko dana šaljem poruku maltene identičnu kao onu prethodnu pa sam zbot toga pomislio da si možda na to mislio :)

Uh, taj deo je stvarno konfuzan, slažem se. Ako te stvarno zanima meni nije teško da objasnim svaki detalj na kom si se zaglavio, slobodno napiši, ali ako ipak misliš da je previše egzotično opet se ne ljutim, kao što rekoh u prošloj poruci svako bira šta ga zanima a šta ne :)

_{[Ovu poruku je menjao Bojan Basic dana 24.03.2006. u 10:27 GMT+1]}

Ma ne, nisam se zaglavio, shvatio sam tvoje resenje nego kazem da kada sam ja pokusavao da resim zadatak onda sam dosao dotle da je funkcija injekcija (to nije bilo tesko) ali posle nisam mogao da mrdnem odatle. Sada kada sam video tvoje resenje mogu samo da ti cestitam :-)

_{[Ovu poruku je menjao srki dana 24.03.2006. u 12:20 GMT+1]}

Kad smo već kod toga zanima me da li ti je rešenje isto kao moje? Ja sam najpre pogrešno mislio da sam to dokazao (posle sam našao očiglednu grešku), pa sam posle mislio da je lako i odlagao sam za kraj, i na kraju sam se zapetljao i nisam našao ništa jednostavnije od onog što piše gore. Ako imaš jednostavnije rešenje tog dela zadatka bilo bi lepo da i to vidimo.

Nešto sam ponovo čitao ovaj zadatak i primetio sam neshvatljivu grešku. Na sreću, može se (relativno jednostavno) ispraviti, pa to ovom prilikom činim.

Jasno, skraćivanje izraza u posmatranoj kongruenciji ne dolazi u obzir, jer niko ne garantuje da su i uzajamno prosti. (Kontraprimer: , ali iz ovoga ne sledi da je .) Ovaj pasus potrebno je sasvim prepraviti, npr. ovako.

Primetimo da je nemoguće , jer bi u suprotnom važilo i sada bilo da odaberemo i , bilo i , ni ni ne bi bile fiksne tačke, a ustanovili smo da (bar) jedna od njih jeste. Prema tome (naravno, jasno je da ni ne dolazi u obzir). Pogledajmo za momenat šta će biti ako su i „neodgovarajući“ (značenje ovog pojma ubrzo će postati jasno): ako je iz , dobijamo , pa iz toga sledi da je i (upamtimo, jer je !), što će biti kongruencija koju ćemo posmatrati ako se zadesi ovaj slučaj; ukoliko je ali (ili obratno), jednostavno ćemo posmatrati kongruenciju . U svim slučajima (originalnom i dvama specijalnima) imamo kongruencije takve da su koeficijenti uz između i (uključujući i njih). Uočimo sada brojeve koji se preslikavaju, redom, u levu i desnu stranu posmatrane kongruencije, takve da važi (iz prethodnog razmatranja, jasno je da su i važi ). Sada je . Kako važi , jasno je da slike različitih brojeva iz ovog intervala moraju biti različite, a ne iste kako smo upravo dobili. Kontradikcija.

Nešto mi nije jasno u ovom rešenju.
Ako sam dobro shvatio, umesto dokazivanja originalnog zadatka, ti dokazujes konkretniju tvrdnju:
Funkcionalna jednačina ima rešenja za i samo za neparane i za .
Zatim su pronađene funkcije za slučajeve i za , što mi je sasvim jasno.
Ostalo je da se dokaže nepostojanje funkcije za slučaj 2) i slučaj 3) parno , čime se iscrpljuje sav skup celih brojeva .
Zapeo sam već kod slučaja 2). Nije mi jasan dokaz tvrđenja (**). Možeš li to malo pojasniti?

Zapravo, nije to ništa konkretnije, ne može se dati manje konkretan a potpun odgovor. Pitanje je „kad ima rešenja“, a ja odgovaram kad ih ima i dokazujem da ih zaista ima samo tad (tj. da nisam nešto propustio).



Svakako, vrlo rado (sasvim sam svestan zapetljanosti dokaza, pa mi je drago kad neko uopšte pokuša da ga pročita i shvati; na kraju krajeva, ipak sam na njega potrošio neko vreme svoga života, pa ne bi voleo da prođe nezapaženo ).

Tvrđenje kaže da za svako važi: u skupu najmanji element je upravo (štaviše, on je jedini najmanji element; to nije dovoljno precizirano u samoj postavci tvrđenja, ali je jasno iz dokaza). Dokazujemo matematičkom indukcijom.

Za treba dokazati, jasno, da je najmanja vrednost celog kodomena. Pretpostavimo (u želji da dobijemo kontradikciju) suprotno, tj. da se minimum dostiže za neko (umesto za ). Kada u postavku uvrstimo , dobijamo , tj. postoji vrednost u kodomenu koja je (za ) manja od . Kontradikcija, jer smo pretpostavili da je minimum; dakle, baza indukcije je dokazana.

U indukcijskoj hipotezi pretpostavimo (standardno) da tvrđenje važi za sve brojeve manje od , pa dokazujemo da onda važi i za .

Slično kao prilikom dokaza baze indukcije, pretpostavimo suprotno, tj. da je među brojevima najmanji neki , pri čemu je . Iz postavke dobijamo . Ako dokažemo da je (drugim rečima: da je ), dobijamo željenu kontradikciju (jer, jasno, tada ne bi bila najmanja vrednost iz posmatranog skupa, a pretpostavili smo da jeste). U to ime, primetimo da za svaki broj važi : zaista, iz indukcijske hipoteze za dobijamo da je minimalna vrednost u skupu , pa važi ; slično, iz IH za dobijamo da je minimalna vrednost u skupu , pa važi ; primenjujemo ovo „unazad“, i kad sve sklopimo u jedan red dobijamo kad god je (da je jasno je, pošto je kodomen funkcije skup prirodnih brojeva). Primetimo da ovo implicira , jer ne možemo više „sabiti“ prirodne brojeve u ovaj niz. Pošto je , neka to bude naše , pa imamo ; međutim, sada ovu vrednost s leve strane možemo uzeti da bude , pa još jednom primenom iste formule imamo . Prema tome, eto nama željene kontradikcije.

Ovom kontradikcijom se i završava dokaz tvrđenja . Lako se vidi da iz tog tvrđenja neposredno sledi da je funkcija da je monotono rastuća, a to dalje koristimo u dokazu.

Možda sam se sad previše raspričao, ali „od viška glava ne boli“. Čekam dalja pitanja, ako ih bude bilo.

Da, dugujem ti odgovor, potpuno sam zaboravio na ovu temu. Imam jednostavnije resenje inace ne bih rekao da je lako .
Ti si dokazao (pod pretpostavkom da f-ja nije injekcija) da je najveca slika, da postoji neko tako da je (greskom si napisao da se to slika u 1) i da slike funkcije pripadaju skupu ali si posle zakomlikovao gledanjem periodicnosti i sl.

Evo kako sam ja odatle resio :
primetimo da iz sledi da ne postoji tako da je (jer je pozitivno). To je cinjenica (a).

Dalje primetimo da je razlicito od 1. To znaci da postoji neko tako da je . Odatle imamo . Iz dobijamo sto je u kontradikciji sa cinjenicom (a).

_{[Ovu poruku je menjao srki dana 25.03.2007. u 13:55 GMT+1]}

Svaka čast! Vredelo je čekati godinu dana za ovo pojednostavljenje. :)