# 2009 IMO Problems/Problem 5

## Problem

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

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

*Author: Bruno Le Floch, France*

## Solution

Answer: The only such function is .

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, , are sides of a non-degenerate triangle then .

Proof. In this case , therefore . By the same reason, . Therefore .

Let . Now consider the given condition for . By Lemma we get that

First, suppose . Then is a periodic function. But then is bounded by a constant , i.e. . Then take, . We get that and are sides of the triangle, but the first number is greater than and other two are less than , which is imposible. We get the contradiction, so could not be greater than 1.

So .

Property 1. For any

Proof. Consider the given condition for , and use Lemma.

Property 2. For any and

Proof. Consider the given condition for , and use triangle inequality and Property 1.

Let .

Property 3. For any and

Proof. Follows from Property 2.

Property 4. For any , , ,

Proof. Follows from Property 3.

Property 5. For any , there is , s.t. .

Proof. Because of the Property 1.

Property 6. .

Proof. Suppose, for some , . Without lost of generality we can assume that . Then there is a number , such than any could be represented as , where . Then . That contradicts to the Property 5.

Therefore by definion of , .