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 00: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 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 , .
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 |