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,f(b)$](http://latex.artofproblemsolving.com/8/e/6/8e645a0393a2bb5633d525e276321203781753af.png)
![$f(b+f(a)-1)$](http://latex.artofproblemsolving.com/7/e/2/7e24db20845eba2e50f55b74a222d4ef4858c53a.png)
(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
![$f(b)=f(b+u-1)$](http://latex.artofproblemsolving.com/4/8/0/4805b0a000399510ffe1dcbafe0605026493f1e9.png)
![$b$](http://latex.artofproblemsolving.com/8/1/3/8136a7ef6a03334a7246df9097e5bcc31ba33fd2.png)
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
![$f(f(x)) = x$](http://latex.artofproblemsolving.com/5/7/7/577d36f19d8078a378cba936d43eb40151b1e13d.png)
Proof. Consider the given condition for ,
and use Lemma.
Property 2. For any and
![$f(x+1)+f(y) > f(x+y)$](http://latex.artofproblemsolving.com/c/d/8/cd865d6d5edaa36b8e186fa54eb2412a1d9f7170.png)
Proof. Consider the given condition for ,
and use triangle inequality and Property 1.
Let .
Property 3. For any and
![$g(x)+g(y) \ge g(x+y)$](http://latex.artofproblemsolving.com/8/5/1/851e339147cbab9b9c06e6686e20fdf50c5040c3.png)
Proof. Follows from Property 2.
Property 4. For any ,
,
,
![$g(nx)+g(my) \ge g(nx+my)$](http://latex.artofproblemsolving.com/a/9/7/a97d9f69a33c036253e7e9e9df932584c5fb1a30.png)
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 ,
.
Akopylov 00:51, 12 August 2010 (UTC)