2009 IMO Problems/Problem 5

Problem

Determine all functions $f$ from the set of positive integers to the set of positive integers such that, for all positive integers $a$ and $b$ , there exists a non-degenerate triangle with sides of lengths

$a,f(b)$ and $f(b+f(a)-1)$ .

(A triangle is non-degenerate if its vertices are not collinear.)

Author: Bruno Le Floch, France

Solution

Answer: The only such function is $f(x)=x$ .

It is easy to see that this function satisfy the condition. We are going to proof that this is the only such function.

We start with

Lemma. If 1, $a$ , $b$ are sides of a non-degenerate triangle then $a=b$ .

Proof. In this case $a<b+1$ , therefore $a \le b$ . By the same reason, $b \le a$ . Therefore $a=b$ .

Let $u=f(1)$ . Now consider the given condition for $a=1$ . By Lemma we get that

$f(b)=f(b+u-1)$ for any $b$ .

First, suppose $u>1$ . Then $f$ is a periodic function. But then $f$ is bounded by a constant $M$ , i.e. $f(x)<M$ . Then take, $a>2M$ . We get that $a,f(b)$ and $f(b+f(a)-1)$ are sides of the triangle, but the first number is greater than $2M$ and other two are less than $M$ , which is imposible. We get the contradiction, so $u$ could not be greater than 1.

So $u=f(1)=1$ .

Property 1. For any $x$

$f(f(x)) = x$

Proof. Consider the given condition for $a=x$ , $b=1$ and use Lemma.

Property 2. For any $x$ and $y$

$f(x+1)+f(y) > f(x+y)$

Proof. Consider the given condition for $a=f(x+1)$ , $b=y$ and use triangle inequality and Property 1.

Let $g(x)=f(x+1)-1$ .

Property 3. For any $x$ and $y$

$g(x)+g(y) \ge g(x+y)$

Proof. Follows from Property 2.

Property 4. For any $x$ , $y$ , $m$ , $n$

$g(nx)+g(my) \ge g(nx+my)$

Proof. Follows from Property 3.

Property 5. For any $n$ , there is $k>n$ , s.t. $g(k) \ge k$ .

Proof. Because of the Property 1.

Property 6. $g(x)=x$ .

Proof. Suppose, for some $x$ , $g(x)=y\ne x$ . Without lost of generality we can assume that $x<y$ . Then there is a number $n$ , such than any $k>n$ could be represented as $k=ax+by$ , where $a>b$ . Then $g(k)=g(ax+by)\ge ag(x)+bg(y)=ay+bx>ax+by=k$ . That contradicts to the Property 5.

Therefore by definion of $g$ , $f(x)=x$ .

Page

Toolbox

Search

2009 IMO Problems/Problem 5

Problem

Solution