Za koje k funkcionalna jednačina ima rešenja?

Za koje vrednosti broja postoji funkcija takva da važi .

Mučim se već tri dana sa ovim zadatkom, nije da mi je rešenje nešto posebno bitno rešenje ali baš mi je zagolicao maštu. Ono što me zanima su slučajevi parnih , ostale sam rešio (neću još da napišem rešenje da bi svako sam mogao da pokuša, ako ne uspete a zanima vas javite). Nagađam da za njih nema rešenja, ali nikako mi ne uspeva da dokažem. Najdalje što sam stigao u tom slučaju je da funkcija mora biti injektivna (ovo možete slobodno koristiti ako vam zatreba u rešavanju pošto za to imam dokaz). Takođe, dovoljno je pokazati da je , ali ni to nisam uspeo. Ako se zaglavite na istom mestu kao i ja pokušajte da rešite bar ove slučajeve koje sam i ja rešio, da uporedimo razmišljanja, i, naravno, kao i uvek dobrodošao je i svaki, makar i neuspešan pokušaj, a ne isključivo gotova rešenja :)

P. S. Namerno nisam u naslovu stavio prefiks [Zadatak] pošto to radim u slučaju kada znam rešenje i želim da ga podelim sa vama, a ovde svi zajedno rešavamo pa ko prvi stigne do kraja :)

---

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.

---