Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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…')
 
m (→‎Solution)
(2 intermediate revisions by 2 users not shown)
Line 9: Line 9:
 
''Author: Bruno Le Floch, France''
 
''Author: Bruno Le Floch, France''
  
−
--[[User:Bugi|Bugi]] 10:30, 23 July 2009 (UTC)Bugi
+
== 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>.

Revision as of 13:05, 10 July 2012

Problem

Determine all functions $f$ from the set of positive integers to the set of positive integers such that, for all positive integers $a$ and $b$, there exists a non-degenerate triangle with sides of lengths

$a,f(b)$ and $f(b+f(a)-1)$.

(A triangle is non-degenerate if its vertices are not collinear.)

Author: Bruno Le Floch, France

Solution

Answer: The only such function is $f(x)=x$.

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, $a$, $b$ are sides of a non-degenerate triangle then $a=b$.

Proof. In this case $a<b+1$, therefore $a \le b$. By the same reason, $b \le a$. Therefore $a=b$.

Let $u=f(1)$. Now consider the given condition for $a=1$. By Lemma we get that

$f(b)=f(b+u-1)$ for any $b$.

First, suppose $u>1$. Then $f$ is a periodic function. But then $f$ is bounded by a constant $M$, i.e. $f(x)<M$. Then take, $a>2M$. We get that $a,f(b)$ and $f(b+f(a)-1)$ are sides of the triangle, but the first number is greater than $2M$ and other two are less than $M$, which is imposible. We get the contradiction, so $u$ could not be greater than 1.

So $u=f(1)=1$.

Property 1. For any $x$

$f(f(x)) = x$

Proof. Consider the given condition for $a=x$, $b=1$ and use Lemma.

Property 2. For any $x$ and $y$

$f(x+1)+f(y) > f(x+y)$

Proof. Consider the given condition for $a=f(x+1)$, $b=y$ and use triangle inequality and Property 1.

Let $g(x)=f(x+1)-1$.

Property 3. For any $x$ and $y$

$g(x)+g(y) \ge g(x+y)$

Proof. Follows from Property 2.

Property 4. For any $x$, $y$, $m$, $n$

$g(nx)+g(my) \ge g(nx+my)$

Proof. Follows from Property 3.

Property 5. For any $n$, there is $k>n$, s.t. $g(k) \ge k$.

Proof. Because of the Property 1.

Property 6. $g(x)=x$.

Proof. Suppose, for some $x$, $g(x)=y\ne x$. Without lost of generality we can assume that $x<y$. Then there is a number $n$, such than any $k>n$ could be represented as $k=ax+by$, where $a>b$. Then $g(k)=g(ax+by)\ge ag(x)+bg(y)=ay+bx>ax+by=k$. That contradicts to the Property 5.

Therefore by definion of $g$, $f(x)=x$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_IMO_Problems/Problem_5&oldid=47608"