2009 IMO Problems/Problem 5
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
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.
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.
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 , .