2009 IMO SL A3

For discussing Olympiad Level Algebra (and Inequality) problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
2009 IMO SL A3

Unread post by rah4927 » Wed Feb 01, 2017 7:44 pm

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) \text{ and } f(b + f(a) - 1).\]
(A triangle is non-degenerate if its vertices are not collinear.)

Source : 2009 IMO SL

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: 2009 IMO SL A3

Unread post by Nirjhor » Wed Feb 01, 2017 9:04 pm

Let $\triangle (a,b,c)$ denote that lengths $a,b,c$ form a valid triangle.

Let $P(a,b)$ denote $\triangle\left(a,f(b),f\left(b+f(a)-1\right)\right)$.

Easy to prove: $\triangle (1,a,b)\Rightarrow a=b$ and $\triangle (2,a,b)\Rightarrow \left|a-b\right|\le 1$.

Now $P(1,b)\Rightarrow f\left(b+f(1)-1\right)=f(b)$. If $f(1)>1$ then $f$ is periodic, hence bounded above. So $P(a,b)$ won't hold as $a\to\infty$. Thus $f(1)=1$ and $P(a,1)\Rightarrow f(f(a))=a$, so $f$ is bijective.

Let $f(2)=t+1$, then $P(2,b)\Rightarrow \left|f(b)-f(b+t)\right|= 1$ (we can discard $0$ since $f$ is bijective). If $f(b+t)=f(b)-1$ then by induction $f(b+st)=f(b)-s$ for all $s\in\mathbb N$ that gives a contradiction for fixed $b$ and $s\to\infty$. So $f(b+t)=f(b)+1$ and by induction $f(b+st)=f(b)+s$.

Now $f\left(1+(t+1)t\right)=f(1)+(t+1)=t+2=f(2)+1=f(2+t)$ and hence by injection, $1+(t+1)t=2+t\Rightarrow t=1$.

So $f(b+1)=f(b)+1$ with $f(1)=1$, by induction $f(n)=n$ for all $n\in\mathbb N$.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: 2009 IMO SL A3

Unread post by Thanic Nur Samin » Thu Feb 02, 2017 1:57 pm

Nirjhor wrote:Let $\triangle (a,b,c)$ denote that lengths $a,b,c$ form a valid triangle.

Let $f(2)=t+1$, then $P(2,b)\Rightarrow \left|f(b)-f(b+t)\right|= 1$ (we can discard $0$ since $f$ is bijective). If $f(b+t)=f(b)-1$ then by induction $f(b+st)=f(b)-s$ for all $s\in\mathbb N$ that gives a contradiction for fixed $b$ and $s\to\infty$. So $f(b+t)=f(b)+1$ and by induction $f(b+st)=f(b)+s$.
But doesn't that only hold for individual $b$'s? Of course, since the function is bijective and the images of the arithmatic sequence differ by exactly once then if it decreases first, then it can't increase again which leads to the same solution, but I think that should have been mentioned.

Other than that, exactly same solution as mine! Great job.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply