A mysterious function So, let $f$ be a function mapping the positive integer to the positive integer.
Assume that the function $f$ has these properties:

(1) $f(2)=2$,
(2) $f(mn)=f(m)f(n)$,
(3) $f(m)>f(n)$ for $m>n$.

What can we say about $f(1983)$ and more generally about $f(n)$ ?
 A: By strong induction you can show that for all $n$: $f(n)=n$
Base: Note that $2=f(2)=f(2\cdot 1) = f(2)\cdot f(1) = 2 \cdot f(1)$, and so $f(1)=1$. And $f(2)=2$
Step: 
Inductive Hypothesis: For any $k<n$ we have that $f(k)=k$
Now consider $f(n)$. 
Two cases: $n$ is even or $n$ is odd.
If $n$ is even, then $n=2m$ for some integer $m$, and since $m <n$ we have by inductive hypothesis that $f(m)=m$. 
Therefore $$f(n)=f(2m)=f(2)\cdot f(m) = 2 \cdot f(m) = 2m = n$$
If $n$ is odd, then $n=2m+1$ for some integer $m$ where $m < n$ and where $m+1<n$, and hence by inductive hypothesis $f(m)=m$ and $f(m+1)=m+1$. 
Therefore, $$f(2m)=f(2)\cdot f(m)=2m$$
Also, $$f(2m+2)= f(2(m+1))=f(2)f(m+1)=2(m+1)$$  
But we have that $$f(2m)<f(2m+1)<f(2m+2)$$ and so $$2m<f(2m+1)<2m+2$$ and since this is a function from integers to integers, it must be that $$f(n)=f(2m+1)=2m+1=n$$
A: By $(1)$ and $(2)$, it is easy to see that $f(1)=1$.
Then by strong induction, 


*

*if $\forall m<2n, f(m)=m$, then by $(2)$, $$f(2n)=2f(n)=2n,$$ and 

*if $\forall m<2n+1, f(m)=m$, then by $(2)$ and $(3)$, $$2f(n)=2n<f(2n+1)<2f(n+1)=2n+2.$$
So for all integers, $f(n)=n$. The base cases $f(1)=1,f(2)=2$ are sufficient.
