Difference between revisions of "2009 IMO Problems/Problem 5"
m |
m (→Solution) |
||
Line 54: | Line 54: | ||
Proof. Suppose, for some <math>x</math>, <math>g(x)=y\ne x</math>. Without lost of generality we can assume that <math>x<y</math>. Then there is a number <math>n</math>, such than any <math>k>n</math> could be represented as <math>k=ax+by</math>, where <math>a>b</math>. Then <math>g(k)=g(ax+by)\ge ag(x)+bg(y)=ay+bx>ax+by=k</math>. That contradicts to the Property 5. | Proof. Suppose, for some <math>x</math>, <math>g(x)=y\ne x</math>. Without lost of generality we can assume that <math>x<y</math>. Then there is a number <math>n</math>, such than any <math>k>n</math> could be represented as <math>k=ax+by</math>, where <math>a>b</math>. Then <math>g(k)=g(ax+by)\ge ag(x)+bg(y)=ay+bx>ax+by=k</math>. That contradicts to the Property 5. | ||
− | Therefore by definion of <math>g</math>, <math>f(x)=x</math>. | + | Therefore by definion of <math>g</math>, <math>f(x)=x</math>. |
− | |||
− |
Revision as of 12:05, 10 July 2012
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 ,
.