2003 Pan African MO Problems/Problem 1

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

2003 Pan African MO (Problems)
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All Pan African MO Problems and Solutions

Page

Toolbox

Search

2003 Pan African MO Problems/Problem 1

Problem

Solution

See Also