IMO 2011 Problem 5

Discussion on International Mathematical Olympiad (IMO)
User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:
IMO 2011 Problem 5

Unread post by Moon » Wed Jul 20, 2011 12:34 pm

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers m and n, the difference $f(m) - f(n)$ is divisible by $f(m- n).$ Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m).$
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO 2011 Problem 5

Unread post by Masum » Thu Jul 21, 2011 12:18 am

$f(m-0)|f(m)-f(0)\to f(m)|f(0)$.
$f(0-m)|f(0)-f(m)\to f(-m)|f(m)\to f(m)=f(-m)$.
$f(m+n)=f(m-(-n))|f(m)-f(-n)=f(m)-f(n)$. Since $f(n)\ge f(m),f(n)>f(n)-f(m)\ge f(m+n)$.
Again, $f(n)=f(m+n-m)|f(m+n)-f(m)$.
If $f(m)>f(m+n),f(m)>f(m)-f(m+n)\ge f(n)\ge f(m)$, contradiction.
If $f(m)<f(m+n),f(m+n)>f(m+n)-f(m)\ge f(n)>f(m+n)$, contradiction!
Thus, only $f(m+n)=f(m)$ is possible.
Then $f(m)=f(m+n-n)|f(m+n)-f(n)=f(m)-f(n)\to f(m)|f(n)$.
One one thing is neutral in the universe, that is $0$.

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: IMO 2011 Problem 5

Unread post by Tahmid Hasan » Thu Jul 21, 2011 4:18 pm

$f(m-n) \mid f(m)-f(n)$......(p)
setting $n$ as $0$ in (p)
we get $f(m) \mid f(0)$
setting $m$ as $0$ in (p)
we get $f(-n) \mid f(n)$......(1)
setting $m$ as $0$,$n$ as $-n$ in (p)
we get $f(n) \mid f(-n)$......(2)
so from (1) and (2) we can say
$f(n)=f(-n)$......(3)
setting $m$ as $2n$ in (p)
we get $f(n) \mid f(2n)$ or,$f(2n) \geq f(n)$......(y)
setting $n$ as $-n$ in (p)
we get $f(m+n) \mid f(m)-f(n)$ or, $f(m)-f(n) \geq f(m+n)$......(x)
setting $m$ as $(m+n)$ in (p)
we get $f(m) \mid f(m+n)- f(n)$
if $f(m) \mid f(m+n)$ the proof is complete.so this will be our requirement from now on.
there can be $3$ relations between $f(m+n)$ and $f(m)$
a.$f(m+n)> f(m)$ or,$f(m+n)>f(m)-f(n)$ but this is a contradiction according to (x)
b.$f(m+n)<f(m)$
setting $m$ as $n$ yields $f(2n)<f(n)$ which is a contradiction according to (y)
so $f(m+n)=f(m)$
hence $f(m) \mid f(m+n)$
which was our requirement.
বড় ভালবাসি তোমায়,মা

Hasib
Posts:238
Joined:Fri Dec 10, 2010 11:29 am
Location:খুলনা, বাংলাদেশ
Contact:

Re: IMO 2011 Problem 5

Unread post by Hasib » Fri Jul 22, 2011 12:07 am

I get fully confused. Let $f(x)=x^2$ and $m=3 , n=5$ so, $f(3)=9$, $f(5)=25$ and $f(3-5)=4$ so, $f(3)-f(5)=16$ is divisible by $f(3-5)$ and $f(3)<f(5)$ but $f(5)$ isnt divisible by $f(3)$ what happened? !!!!
A man is not finished when he's defeated, he's finished when he quits.

Hasib
Posts:238
Joined:Fri Dec 10, 2010 11:29 am
Location:খুলনা, বাংলাদেশ
Contact:

Re: IMO 2011 Problem 5

Unread post by Hasib » Fri Jul 22, 2011 12:36 am

Yeah.. I found my fault. The question said for all m, n. Bt my imagination is nt for all (m,n) thats why ... :)
A man is not finished when he's defeated, he's finished when he quits.

User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.

Re: IMO 2011 Problem 5

Unread post by Tahmid Hasan » Fri Jul 22, 2011 4:51 pm

there is a fun fact,this is a constant function.
do you get it now?
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO 2011 Problem 5

Unread post by Masum » Fri Jul 22, 2011 10:41 pm

Tahmid Hasan wrote: there can be $3$ relations between $f(m+n)$ and $f(m)$
a.$f(m+n)> f(m)$ or,$f(m+n)>f(m)-f(n)$ but this is a contradiction according to (x)
b.$f(m+n)<f(m)$
setting $m$ as $n$ yields $f(2n)<f(n)$ which is a contradiction according to (y)
Your first case is right but your second case was wrong. You proved this for $m=n$ which was in fact, always true since $f(m)=f(n)$
One one thing is neutral in the universe, that is $0$.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: IMO 2011 Problem 5

Unread post by *Mahi* » Fri Jul 29, 2011 7:38 pm

Tahmid Hasan wrote:there is a fun fact,this is a constant function.
do you get it now?
This is COMPLETELY wrong.
The function might generate values like $1,1,1,a,a,a,a,1,1,1,k,k,k,1,1...$
There is no guarantee that it must be constant or $m \geq n $ implying $f(m) \geq f(n)$
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: IMO 2011 Problem 5

Unread post by Phlembac Adib Hasan » Sat Mar 22, 2014 3:04 pm

Suppose $P(m,n)\Longrightarrow f(m-n)|f(m)-f(n)$.

$P(n,0)\Longrightarrow f(n)|f(0)\Longrightarrow f(n)$ can attain finitely many distinct values. Let $f(a_1)<f(a_2)<\cdots<f(a_k)$ be those values.

$\begin{array}{lr}P(0,n)\Longrightarrow f(-n)|f(n)\\
P(0,-n)\Longrightarrow f(n)|f(-n)\end{array}\bigg \} f(n)=f(-n)$

Now we'll prove $f(a_i)|f(a_{i+1})$ for $1\leq i\leq k-1$. This will indeed prove $f(a_m)\leq f(a_n)\Longrightarrow f(a_m)|f(a_n)$.

$P(a_{i+1},a_i)\Longrightarrow f(a_{i+1}-a_i)|f(a_{i+1})-f(a_i)>0...(i)$
$\Longrightarrow f(a_{i+1}-a_i)<f(a_{i+1})$.
$\Longrightarrow f(a_{i+1}-a_i)=f(a_i)$ or $f(a_{i-1})...$ or $f(a_1)$
If $f(a_{i+1}-a_i)=f(a_i)$, from (i), we are done. Note that for $i=1$, we are done here. But if $i>1$, we have another case: $f(a_{i+1}-a_i)<f(a_i)...(ii)$. We'll show this is impossible.
$P(a_i,a_i-a_{i+1})\Longrightarrow f(a_{i+1})|f(a_i)-f(a_i-a_{i+1})=f(a_i)-f(a_{i+1}-a_i)>0$ [From (ii)]
$\Longrightarrow f(a_{i+1}) < f(a_i)$. A contradiction.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply