2008 Indonesia MO Problems/Problem 8

Solution 1

Since $f: \mathbb{N}\rightarrow\mathbb{N}$ , we know that $f(n)\ge 1$ .

Let $m$ , $n$ be $1$ , $1$ , respectively. Then, $f(1) + f(2) = f(1)f(1) + 1$ .

Let $m$ , $n$ be $1$ , $2$ , respectively. Then, $f(2) + f(3) = f(1)f(2)+1$

Let $m$ , $n$ be $1$ , $3$ , respectively. Then, $f(3) + f(4) = f(1)f(3)+1$

Let $m$ , $n$ be $2$ , $2$ , respectively. Then, $f(4) + f(4) = f(2)f(2)+1$

From the last 2 equations, we get that $\frac{1}{2}(f(2)^2+1)=f(4)=f(3)(f(1)-1)+1$

Since $f(3) = f(2)(f(1)-1)+1$ , substituting, we get

$\frac{1}{2}(f(2)^2+1)=(f(2)(f(1)-1)+1)(f(1)-1)+1$ $\frac{1}{2}(f(2)^2+1)=f(2)f(1)^2-f(2)f(1)+f(1)-f(2)f(1)-f(2)-1+1$ $f(2)^2+1=2f(2)f(1)^2-2f(2)f(1)+2f(1)-2f(2)f(1)-2f(2)$

If we take modulo of f(2) on both sides, we get

$1 \equiv 2f(1) \mod f(2)$

$2f(1)-1 \equiv 0 \mod f(2)$

Because $f(1) + f(2) = f(1)f(1) + 1$ , we also know that $f(2) = f(1)f(1)-f(1)+1 = f(1)(f(1)-1)+1$ . If $f(1)>1$ , then $f(2)>f(1)$ .

Suppose $f(1)>1$ :

since $f(2)>f(1)$ , we have $2f(2)>2f(1)-1>0$ . Or that $2>\frac{2f(1)-1}{f(2)}>0$ . Thus, $\frac{2f(1)-1}{f(2)}=1$ $2f(1)-1=f(2)=f(1)f(1)-f(1)+1$ $f(1)^2-3f(1)+2=0$ $(f(1)-2)(f(1)-1)=0$ Thus, $f(1)=1$ or $f(1)=2$ .

case 1: $f(1)=1$

Let $m=1$ , and $n$ be an arbitrary integer $\ge 1$ . Then, $f(n) + f(n+1) = f(1)f(n) + 1$ $f(n) + f(n+1) = f(n) + 1$ $f(n+1) = 1$ Thus, $f(n) = 1$ .

case 2: $f(1)=2$

Let $m=1$ , and $n$ be an arbitrary integer $\ge 1$ . Then, $f(n) + f(n+1) = f(1)f(n) + 1$ $f(n) + f(n+1) = 2f(n) + 1$ $f(n+1) = f(n)+1$ This forms a linear line where $f(1)=2$ Thus, $f(n)=n+1$

Upon verification for $f(n) = 1$ , we get $f(mn)+f(m+n)=f(m)f(n)+1$ $1+1=1+1$

Upon verification for $f(n) = n+1$ , we get $f(mn)+f(m+n)=f(m)f(n)+1$ $mn+1+m+n+1=(m+1)(n+1)+1$ $mn+m+n+2=mn+m+n+2$

Thus, both equations, $f(n) = 1$ and $f(n) = n+1$ are valid

Page

Toolbox

Search

2008 Indonesia MO Problems/Problem 8

Solution 1