2003 Pan African MO Problems/Problem 1

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Let $N_0=\{0, 1, 2 \cdots \}$. Find all functions: $N_0 \to N_0$ such that:

(1) $f(n) < f(n+1)$, all $n \in N_0$;

(2) $f(2)=2$;

(3) $f(mn)=f(m)f(n)$, all $m, n \in N_0$.

Solution

Because $f(mn) = f(m)f(n)$, we must have $f(2) = f(2) \cdot f(1)$, so $f(1) = 1$. Thus, $f(0) = 0$.

By trying smaller values, we suspect that $f(n) = n$ for all values in the set $N_0$. To prove this, we would use induction to show that $f(n) = n$ for $0 \le n \le 2^k$ for all integer values of $k$.

The base case works because $f(0) = 0, f(1) = 1, f(2) = 2$. For the inductive step, assume that $f(n) = n$ for $0 \le n \le 2^k$ for an integer value of $k$. To prove this case, we need to prove that all values from $2^k + 1$ to $2^{k+1}$ also work.

Note that $f(2n) = f(2) \cdot f(n) = 2 f(n)$. Therefore, we must have $f(2^{k+1}) = 2 \cdot f(2^k) = 2^{k+1}$. Additionally, given that $m$ is an integer that satisfies $2^{k+1} - 2m - 2 \ge 0$, we must have $f(2^{k+1} - 2m) = 2 \cdot f(2^k - m)$. Since $2^k - m$ is within the range of $0 \le n \le 2^k$, we must have $2 \cdot f(2^k - m) = 2^{k+1} - 2m$. Furthermore, we must also have $f(2^{k+1} - 2m - 2) = 2 \cdot f(2^k - m - 1) = 2^{k+1} - 2m - 2$. Thus, we must have $f(2^{k+1} - 2m - 1) = 2^{k+1} - 2m - 1$. Since $m$ can be any integer that satisfies $2^{k+1} - 2m - 2 \ge 0$, the value $2^{k+1} - 2m - 2$ can be any even integer. Thus all numbers from $0$ to $2^{k+1}$ are represented in the proof, so the inductive step holds.

Therefore, $f(n) = n$ for $0 \le n \le 2^k$ for any integer value of $k$, so the only function $N_0 \to N_0$ that satisfies the three conditions is $\boxed{f(n) = n}$.