Canadian Mathematical Olympiad

Solution:

Let us analyze the properties of $f$.

From property 4, $f(m n) = f(m) f(n)$ for all positive integers $m, n$. This means $f$ is a multiplicative function.

Let us compute $f(1)$:

Take $m = n = 1$:
$$f(1) = f(1 \cdot 1) = f(1) f(1) \implies f(1)^2 = f(1)$$
So $f(1) = 0$ or $f(1) = 1$.

Suppose $f(1) = 0$. Then for any $n$,
$$f(n) = f(n \cdot 1) = f(n) f(1) = f(n) \cdot 0 = 0$$
So $f(n) = 0$ for all $n$, but this contradicts $f(2) = 2$. Therefore, $f(1) = 1$.

Now, $f(2) = 2$ is given.

Let us try to find $f(2^k)$ for $k \geq 1$.

By induction:
- $f(2^1) = f(2) = 2$
- $f(2^2) = f(2 \cdot 2) = f(2) f(2) = 2 \cdot 2 = 4$
- $f(2^3) = f(2 \cdot 2^2) = f(2) f(2^2) = 2 \cdot 4 = 8$

So $f(2^k) = 2^k$ for all $k \geq 1$.

Now, let us consider $f(3)$.

Since $f$ is strictly increasing (property 5), $f(3) > f(2) = 2$ and $f(3)$ is an integer.

Let us compute $f(3^k)$:
- $f(3^1) = f(3)$
- $f(3^2) = f(3) f(3)$
- $f(3^3) = f(3) f(3) f(3) = f(3)^3$

Similarly, $f(6) = f(2 \cdot 3) = f(2) f(3) = 2 f(3)$.

But $f(6)$ must also equal $f(6) = f(3 \cdot 2) = f(3) f(2) = f(3) \cdot 2 = 2 f(3)$, which is consistent.

Now, consider $f(4) = 4$ and $f(3) > 2$.

But $f(4) = 4$ and $f(3)$ is an integer $> 2$ and $f$ is strictly increasing, so $f(3) = 3$ (since $f(3) < f(4) = 4$ and $f(3)$ is an integer $> 2$).

Now, $f(5)$ must be an integer $> f(4) = 4$, so $f(5) \geq 5$.

Let us check $f(10) = f(2 \cdot 5) = f(2) f(5) = 2 f(5)$.
But $f(10) = f(5 \cdot 2) = f(5) f(2) = f(5) \cdot 2 = 2 f(5)$, which is consistent.

Let us try to prove by induction that $f(n) = n$ for all $n$.

Base case: $f(1) = 1$, $f(2) = 2$, $f(3) = 3$.

Suppose $f(k) = k$ for all $k < n$.

If $n$ is composite, say $n = a b$ with $a, b < n$, then
$$f(n) = f(a b) = f(a) f(b) = a b = n$$
If $n$ is prime, then $f(n)$ is an integer $> f(n-1) = n-1$, so $f(n) \geq n$.

But if $f(n) > n$, then $f(n) \geq n+1$.

Consider $f(2 n) = f(2) f(n) = 2 f(n)$. But $2 n$ is less than $2 f(n)$ if $f(n) > n$, which would contradict the strictly increasing property, since $f(2 n) > f(2 n - 1)$, but $f(2 n) = 2 f(n) \geq 2(n+1) = 2 n + 2$, while $f(2 n - 1) = 2 n - 1$ (by induction), so $2 n + 2 > 2 n - 1$, which is always true, but let's check for $n$ large.

But more precisely, suppose $f(n) \geq n+1$, then $f(2 n) = 2 f(n) \geq 2(n+1) = 2 n + 2$, but $2 n$ is the argument, so $f(2 n) \geq 2 n + 2$, but $f(2 n - 1) = 2 n - 1$, so the difference is at least $3$.

But $f$ must be strictly increasing by $1$ at each step, since $f(n)$ is an integer and $f(n) > f(n-1)$, so $f(n) \geq f(n-1) + 1$.

But if $f(n) > n$, then $f(n) \geq n+1$, so $f(n) - f(n-1) \geq 2$ for some $n$, which is not possible if $f$ is strictly increasing by $1$ at each step.

Therefore, $f(n) = n$ for all $n$.

Thus, the only function satisfying all the properties is $f(n) = n$.