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
2009 IMO SL A3
Re: 2009 IMO SL A3
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$.
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.
- Zero.
- Why?
- Because all the poles are in Eastern Europe.
Revive the IMO marathon.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: 2009 IMO SL A3
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.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$.
Other than that, exactly same solution as mine! Great job.
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.