Let $k$ be a natural number. For each function $f : \mathbb{N}\to \mathbb{N}$ define the sequence of functions $(f_{m})_{m\geq 1}$ by $f_{1}= f$ and $f_{m+1}= f \circ f_{m}$ for $m \geq 1$ . Function $f$ is called $k$-nice if for each $n \in\mathbb{N}: f_{k}(n) = f (n)^{k}$. (a) For which $k$ does there exist an injective $k$-nice function $f$ ? (b) For which $k$ does there exist a surjective $k$-nice function $f$ ?
Problem
Source: Serbian Mathematical Olympiad 2007
Tags: function, induction, algebra proposed, algebra
BaBaK Ghalebi
09.06.2007 21:01
hint:first prove $b)$ and then prove $a)$
for $b)$
for $k=1$ the function $f(n)=n$ is trivialy a $1-nice$ surjective function...
so assume that$k>1$mthere doesnt exists any...
assume number $a$ s.t $a$ isnt the $k^{th}$ power of a natural number,then we know that there exists number $c$ s.t $f(c)=a$
and also we know that there exists $b$ s.t $f(b)=c$ with this method we can find a $x$ s.t $f_{k-1}(x)=c$
so we get that $f_{k}(x)=a$ now if $f$ were $k-$nice then we would have $f_{k}(x)=f(x)^{k}=t^{k}$ so we get that $a=t^{k}$ contradiction...
and for $a)$ there exists such finction,I`ll give the function later,there is a method of constructing this function some induction type of method...
lovejrz
10.06.2007 02:36
still dont understand
aviateurpilot
10.06.2007 03:45
lovejrz wrote: still dont understand for $b)$ BaBaK Ghalebi say that if $f$ is a surjective $k$-nice function. then we have $f_{k}$ is surjective and for exemple $\exists x\in\mathbb{N}: f_{k}(x)=2$ so $2=f_{k}(x)=f(x)^{k}$ then $\sqrt[k]{2}=f(x)\in\mathbb{N}$ then $k=1$ and we have $f(n)=n$ is a surjective $1$-nice function. another solution. all f surjective are a surjective $1$-nice function. if $k>1$ $f_{k}$ is a surjective but $f^{k}$ is not surjective then $f_{k}\neq f^{k}$.
BaBaK Ghalebi
10.06.2007 11:15
tnx aviateurpilot I thought $k>1$ I have edited my post tnx...
anonymouslonely
06.02.2013 08:02
aviateurpilot wrote: lovejrz wrote: still dont understand for $b)$ BaBaK Ghalebi say that if $f$ is a surjective $k$-nice function. then we have $f_{k}$ is surjective and for exemple $\exists x\in\mathbb{N}: f_{k}(x)=2$ so $2=f_{k}(x)=f(x)^{k}$ then $\sqrt[k]{2}=f(x)\in\mathbb{N}$ then $k=1$ and we have $f(n)=n$ is a surjective $1$-nice function. another solution. all f surjective are a surjective $1$-nice function. if $k>1$ $f_{k}$ is a surjective but $f^{k}$ is not surjective then $f_{k}\neq f^{k}$. $ f $ must be surjective not $ f_{k} $. the answer for both questions is yes. the second is true because $ f_{k+1}(n)=n^{k} $ and we only have to prove the existence of such a function. for the first we can construct some "chains".