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$.

Solution

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