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"

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>.
−
 
 
−
[[User:Akopylov|Akopylov]] 00:51, 12 August 2010 (UTC)
 

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"