Neocijenjeno
10. veljače 2013. 12:57 (11 godine, 5 mjeseci)
Find all functions
![f: \mathbb{N} \rightarrow \mathbb{N}](/media/m/c/3/e/c3e922e496d1f497166720b9e7f9b257.png)
such that
![\forall n \in \mathbb{N}](/media/m/8/9/7/897974980807b4e362f21dfaa0c6630a.png)
%V0
Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $\forall n \in \mathbb{N}$
$f(n+1)>f(f(n))$
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Neka je
![a_1<a_2<...<a_n<...](/media/m/2/7/3/273564667aaf481ea7694cd8459d4e22.png)
skup brojeva takvih da postoji
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
takav da je
![f(x_i)=a_i \forall i](/media/m/4/1/a/41a31570ccda6ad59dd2d631ec9887ef.png)
Uzmimo
![x:f(x)=a_1](/media/m/1/3/6/1364185713868e5b6df41ed616fc0f40.png)
Ako
![x>1](/media/m/9/7/2/9720ec4e55d8a288627aa31a9b2681bc.png)
tada
![f(x)>f(f(x-1)) \newline a_1>f(f(x-1))](/media/m/a/c/4/ac45123ec3cc5c60cd30700a983ab29f.png)
Kontradikcija!
Dakle
![x=1](/media/m/3/4/9/3491fdc1148836187540039de445a211.png)
Uzmimo sada
![x:f(x)=a_2](/media/m/5/9/1/591a8bf6420bdc1eb7649a9bf09e191e.png)
![f(x)>f(f(x-1)) \newline a_2 > f(f(x-1)) \newline f(f(x-1))=a_1 \newline f(x-1)=1](/media/m/e/c/1/ec1f8998ee6bc3b09988bfc5de49366b.png)
To znaci da je broj
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
pogoden funkcijom, pa je ocito
![a_1=1](/media/m/9/3/d/93d3f0e1eb9cd0424cc4b006bc33004e.png)
![f(f(x-1))=1 \newline f(x-1)=1 \newline x-1=1 \newline x=2](/media/m/3/d/e/3de934990b96d9fce7ed44ad0ac242db.png)
Pretpostavimo sada za indukciju da smo pokazali da je
![f(1)=a_1,f(2)=a_2,...,f(n)=a_n](/media/m/3/2/2/3225e49876e28a1913274dbf676cd305.png)
i
![a_1=1,...,a_{n-1}=n-1](/media/m/0/1/5/015ee9f588e88b88302b8fa66c6dbba3.png)
I da
![f(x)=a_i \Rightarrow x=i \forall i \leqslant n](/media/m/4/d/5/4d567c8622ce10c1e88e2a991dcd6271.png)
Uzmimo
![x:f(x)=a_{n+1}](/media/m/2/6/5/265f7bd3fe2fc91db5480508f794f31d.png)
![f(x)>f(f(x-1)) \newline f(f(x-1)) \in \{a_1,...,a_n\} \newline f(x-1) \in \{1,...,n\}](/media/m/0/8/d/08d4a3e4316c219df637c48ca71a7319.png)
Kada bi
![f(x-1)<n](/media/m/5/b/7/5b7d10e1e4bbd470be404b107938c1e4.png)
tada
![x<n+1](/media/m/d/7/c/d7cec27229bf8901001e1ee7ad7da468.png)
pa
![f(x)<a_{n+1}](/media/m/8/b/d/8bd29dbb9560e558ac4cb71a4a8b7006.png)
Kontradikcija!
Dakle
![f(x-1)=n](/media/m/9/6/c/96c92d53502b1a765b43c6bbd369a14a.png)
pa je
![a_n=n](/media/m/1/3/b/13b3399374bfb863c3cc45e7bd16166f.png)
![f(x-1)=n=a_n \newline x-1 =n \newline x=n+1](/media/m/9/7/7/977519849699d42209c1a75355de54f1.png)
Time smo dovrsili korak indukcije i pokazali da je jedina funkcija
%V0
Neka je $a_1<a_2<...<a_n<...$ skup brojeva takvih da postoji $x$ takav da je $f(x_i)=a_i \forall i$
Uzmimo $x:f(x)=a_1$
Ako $x>1$ tada
$f(x)>f(f(x-1)) \newline a_1>f(f(x-1))$
Kontradikcija!
Dakle $x=1$
Uzmimo sada $x:f(x)=a_2$
$f(x)>f(f(x-1)) \newline a_2 > f(f(x-1)) \newline f(f(x-1))=a_1 \newline f(x-1)=1$
To znaci da je broj $1$ pogoden funkcijom, pa je ocito $a_1=1$
$f(f(x-1))=1 \newline f(x-1)=1 \newline x-1=1 \newline x=2$
Pretpostavimo sada za indukciju da smo pokazali da je
$f(1)=a_1,f(2)=a_2,...,f(n)=a_n$
i $a_1=1,...,a_{n-1}=n-1$
I da $f(x)=a_i \Rightarrow x=i \forall i \leqslant n$
Uzmimo $x:f(x)=a_{n+1}$
$f(x)>f(f(x-1)) \newline f(f(x-1)) \in \{a_1,...,a_n\} \newline f(x-1) \in \{1,...,n\}$
Kada bi $f(x-1)<n$ tada $x<n+1$ pa $f(x)<a_{n+1}$ Kontradikcija!
Dakle $f(x-1)=n$ pa je $a_n=n$
$f(x-1)=n=a_n \newline x-1 =n \newline x=n+1$
Time smo dovrsili korak indukcije i pokazali da je jedina funkcija $f(n)=n$