1969 Canadian MO Problems/Problem 8

Revision as of 18:53, 28 July 2006 by 4everwise (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

Solution

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