[Zadatak]: Funkcionalna jednačina iz teorije brojeva

[Zadatak]: Funkcionalna jednačina iz teorije brojeva 03.06.2006. u 00:22 · pre 248 meseci #1

Nije ništa previše teško, mojih ruku delo, čuvao sam ga jedno vreme za neko eventualno takmičenje ali pošto su ovogodišnja takmičenja prošla a zadatak nije bio izabran mogu da ga objavim ovde, pa ako neko želi neka se malo pozabavi. Imam dva prilično različita rešenja, nadam se da će vam se svideti (ali to, naravno, posle).

Naći sve funkcije $f:\textbf{N}\to\textbf{N}$ koje za svako $n$ ispunjavaju sledeće uslove:

1) $f(n+1)\mid n$ ;

2) $f\left(f\left(\frac{n}{f(n+1)}\right)+f(n+1)\right)=n$ .

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 03.06.2006. u 02:02 · pre 248 meseci #2

Neka je $f(n+1)=\delta$ , onda prema prvom uslovu imamo $n=\delta\cdot d$ , a prema drugom uslovu imamo $f(f(d)+\delta)=n$ .

Ako je $n>1$ , onda važi $f(n)|n-1\Rightarrow f(n)<n$ .
Specijalno, ako je $d>1$ , onda je i $f(d)< d$ pa važi $f(d)+\delta<d+\delta$ .

Za svako celo $x>1$ i $y>1$ važi $x+y\le xy$ .
( ${1\over x}+{1\over y}\le {1\over 2}+{1\over 2}=1$ )

Dakle, ako bi bilo i $d>1$ i $\delta>1$ , onda bismo imali da je $d+\delta\le d\cdot\delta=n$ , pa bi moralo da bude $n=f(f(d)+\delta)<f(d)+\delta< n$ a to je kontradikcija.

Znači, mora biti $d=1$ ili $\delta=1$ .

Ne može biti $\delta=1$ , jer bi to (u slučaju da je $n>1$ ) vodilo ka $n=f(f(\frac{n}{f(n+1)})+f(n+1))=f(f(n)+1)<f(n)+1\le n-1+1=n$ što je kontradikcija.

Najzad, vidimo da je $d=1$ tj. $f(n+1)=n$ .

Neka je $f(1)=a$ , onda imamo $n=f(f(\frac{n}{f(n+1)})+f(n+1))=f(f(1)+n)=f(a+n)|n+a-1$ tj.
$n|n+a-1\Rightarrow n|a-1$ - pošto ovo poslednje mora da važi za svako $n>1$ jasno je da mora biti $a=1$ .

Dakle, jedino rešenje je $f(n)=\cases{1,&$n=1$\cr n-1,&$n>1$}$

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 03.06.2006. u 02:35 · pre 248 meseci #3

Lepo, čestitam.

Evo i moja dva obećana rešenja.

Rešenje 1:

Iz prvog uslova zadatka za $n=1$ dobijamo $f(2)\mid 1$ iz čega direktno sledi $f(2)=1$ . Dokazaćemo indukcijom da je $f(n)=n-1$ za sve $n\geq 2$ . Neka za svako $2\leq k\leq n$ važi $f(k)=k-1$ . Kako je
$f\left(f\left(\frac n{f(n+1)}\right)+f(n+1)\right)=n\quad(1)$
sledi da je
$f\left(\frac n{f(n+1)}\right)+f(n+1)>n\quad(2)$
(u suprotnom bi, na osnovu induktivne hipoteze, leva strana relacije $(1)$ bila manja od $n$ ). Očigledno je $1\leq f(n+1)\leq n$ . Pretpostavimo da je $f(n+1)<n$ . Sada je $2\leq\frac{n}{f(n+1)}$ pa na osnovu induktivne hipoteze imamo $f\left(\frac n{f(n+1)}\right)=\frac n{f(n+1)}-1$ . Uvrštavanjem ovoga u $(2)$ imamo:
$\frac n{f(n+1)}-1+f(n+1)>n$
$n-f(n+1)+f(n+1)^2-nf(n+1)>0$
$(f(n+1)-n)(f(n+1)-1)>0$
Izraz u drugoj zagradi je nenegativan pa je $f(n+1)>n$ što je kontradikcija. Sledi da je pretpostavka netačna pa mora biti $f(n+1)=n$ . Preostaje još da nađemo vrednost $f(1)$ . Imamo da je
$n=f\left(f\left(\frac n{f(n+1)}\right)+f(n+1)\right)=f\left(f\left(\frac nn\right)+n\right)=f(f(1)+n)=f(1)+n-1$
iz čega sledi $f(1)=1$ . Lako se proverava da funkcija
$f(n)=\left\{\begin{array}{ll}1,&n=1\\n-1,&n\geq 2\end{array}\right.$
zaista ispunjava uslove zadatka.

Rešenje 2:

Iz prvog uslova zadatka sledi
$f\left(f\left(\frac n{f(n+1)}\right)+f(n+1)\right)\mid f\left(\frac n{f(n+1)}\right)+f(n+1)-1$
što u kombinaciji sa drugim uslovom daje
$n\mid f\left(\frac n{f(n+1)}\right)+f(n+1)-1\quad(1)$
Pošto $f(n+1)\mid n$ sledi da je $f(n+1)\leq n$ . Slično, ukoliko pretpostavimo da za neko $n$ važi $f(n+1)\not=n$ , iz $f\left(\frac n{f(n+1)}\right)\mid \frac n{f(n+1)}-1$ sledi $f\left(\frac n{f(n+1)}\right)\leq\frac n{f(n+1)}-1$ , i uvrštavanjem dobijene dve nejednakosti u relaciju $(1)$ dobijamo
$n\mid f\left(\frac n{f(n+1)}\right)+f(n+1)-1\leq\frac n{f(n+1)}-1+n-1<2n$
Dakle, da bi važila naznačena deljivost mora biti
$n=f\left(\frac n{f(n+1)}\right)+f(n+1)-1$
$n+1=f\left(\frac n{f(n+1)}\right)+f(n+1)$
$f(n+1)=f\left(f\left(\frac n{f(n+1)}\right)+f(n+1)\right)$
$f(n+1)=n$
Ovo je kontradikcija sa našom pretpostavkom. Zaključili smo da za svako $n$ važi $f(n+1)=n$ . Preostaje još da nađemo vrednost $f(1)$ , a ovo se radi isto kao u prethodnom rešenju.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 04.06.2006. u 18:25 · pre 248 meseci #4

Lep zadatak Basicu.. .Sto ga nisi sacuvao za naredne godine?

Potpis

Don’t do drugs, sleep deprivation is better.

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 04.06.2006. u 18:39 · pre 248 meseci #5

Ako nije prošao ove godine verovatno iz istog razloga ne bi ni neke naredne (predlagao sam ga za republičko, tu je bio previše težak, onda posle za savezno, tu ne znam šta beše razlog). Osim toga, prilično sam se razočarao u situaciju u Društvu matematičara (kao što sam jednom rekao, i dok sam bio takmičar znao sam da je loše, ali nisam znao da je baš ovoliko loše) pa ne znam ni da li ću se više baktati tim, a ako i budem odlučio da nastavim, do sledeće godine ću verovatno smisliti još zadataka - nije mi neophodno da čuvam baš ovaj jedan.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 14.06.2006. u 11:41 · pre 248 meseci #6

A kome ti uopste predlazes i saljes zadatak kad ga smislis?

Potpis

http://www.svijetfizike.com/

Re: [Zadatak]: Funkcionalna jednačina iz teorije brojeva 14.06.2006. u 14:54 · pre 248 meseci #7

Daš nekome koga poznaješ a ko ide na sastanak povodom izbora zadataka (naravno, moraju svi da znaju ko si zbog garancije da nisi nikome rekao).

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Forum kao aplikacija na telefonu

Srodne teme