1969 Canadian MO Problems/Problem 8

Problem

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

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

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

3) $f(2)=2$ ;

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

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

Prove that $f(n)=n$ .

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

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

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

1969 Canadian MO (Problems)
Preceded by Problem 7	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 •	Followed by Problem 9