1969 Canadian MO Problems/Problem 8

Problem

Let $\displaystyle f$ be a function with the following properties:

1) $\displaystyle f(n)$ is defined for every positive integer $\displaystyle n$ ;

2) $\displaystyle f(n)$ is an integer;

3) $\displaystyle f(2)=2$ ;

4) $\displaystyle f(mn)=f(m)f(n)$ for all $\displaystyle m$ and $\displaystyle n$ ;

5) $\displaystyle f(m)>f(n)$ whenever $m>n$ .

Prove that $\displaystyle f(n)=n$ .

It's easily shown that $\displaystyle f(1)=1$ and $\displaystyle f(4)=4$ . Since $\displaystyle f(2)<f(3)<f(4),$ $\displaystyle f(3) = 3.$

Now, assume that $\displaystyle f(2n+2)=f(2(n+1))=f(2)f(n+1)=2n+2$ is true for all $\displaystyle f(k)$ where $\displaystyle k\leq 2n.$

It follows that $\displaystyle 2n<f(2n+1)<2n+2.$ Hence, $\displaystyle f(2n+1)=2n+1$ , and by induction $\displaystyle f(n) = n.$