Difference between revisions of "2009 IMO Problems/Problem 5"
(Created page with '== Problem == Determine all functions <math>f</math> from the set of positive integers to the set of positive integers such that, for all positive integers <math>a</math> and <m…') |
|||
(3 intermediate revisions by 2 users not shown) | |||
Line 9: | Line 9: | ||
''Author: Bruno Le Floch, France'' | ''Author: Bruno Le Floch, France'' | ||
− | -- | + | == Solution == |
+ | |||
+ | Answer: The only such function is <math>f(x)=x</math>. | ||
+ | |||
+ | 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, <math>a</math>, <math>b</math> are sides of a non-degenerate triangle then <math>a=b</math>. | ||
+ | |||
+ | Proof. In this case <math>a<b+1</math>, therefore <math>a \le b</math>. By the same reason, <math>b \le a</math>. Therefore <math>a=b</math>. | ||
+ | |||
+ | Let <math>u=f(1)</math>. Now consider the given condition for <math>a=1</math>. By Lemma we get that | ||
+ | <center> <math>f(b)=f(b+u-1)</math> for any <math>b</math>. </center> | ||
+ | |||
+ | First, suppose <math>u>1</math>. Then <math>f</math> is a periodic function. But then <math>f</math> is bounded by a constant <math>M</math>, i.e. <math>f(x)<M</math>. Then take, <math>a>2M</math>. We get that <math>a,f(b)</math> and <math>f(b+f(a)-1)</math> are sides of the triangle, but the first number is greater than <math>2M</math> and other two are less than <math>M</math>, which is imposible. We get the contradiction, so <math>u</math> could not be greater than 1. | ||
+ | |||
+ | So <math>u=f(1)=1</math>. | ||
+ | |||
+ | Property 1. For any <math>x</math> | ||
+ | <center> <math>f(f(x)) = x</math> </center> | ||
+ | Proof. Consider the given condition for <math>a=x</math>, <math>b=1</math> and use Lemma. | ||
+ | |||
+ | Property 2. For any <math>x</math> and <math>y</math> | ||
+ | <center> <math>f(x+1)+f(y) > f(x+y)</math> </center> | ||
+ | Proof. Consider the given condition for <math>a=f(x+1)</math>, <math>b=y</math> and use triangle inequality and Property 1. | ||
+ | |||
+ | Let <math>g(x)=f(x+1)-1</math>. | ||
+ | |||
+ | Property 3. For any <math>x</math> and <math>y</math> | ||
+ | <center> <math>g(x)+g(y) \ge g(x+y)</math> </center> | ||
+ | Proof. Follows from Property 2. | ||
+ | |||
+ | Property 4. For any <math>x</math>, <math>y</math>, <math>m</math>, <math>n</math> | ||
+ | <center> <math>g(nx)+g(my) \ge g(nx+my)</math> </center> | ||
+ | Proof. Follows from Property 3. | ||
+ | |||
+ | Property 5. For any <math>n</math>, there is <math>k>n</math>, s.t. <math>g(k) \ge k</math>. | ||
+ | |||
+ | Proof. Because of the Property 1. | ||
+ | |||
+ | Property 6. <math>g(x)=x</math>. | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2009|num-b=4|num-a=6}} |
Latest revision as of 01:17, 19 November 2023
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 ,
.
See Also
2009 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |