IMO 2011 Problem 5
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.
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.
Re: IMO 2011 Problem 5
$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)$.
$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$.
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 5
$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.
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.
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 5
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.
Re: IMO 2011 Problem 5
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.
- Tahmid Hasan
- Posts:665
- Joined:Thu Dec 09, 2010 5:34 pm
- Location:Khulna,Bangladesh.
Re: IMO 2011 Problem 5
there is a fun fact,this is a constant function.
do you get it now?
do you get it now?
বড় ভালবাসি তোমায়,মা
Re: IMO 2011 Problem 5
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)$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)
One one thing is neutral in the universe, that is $0$.
Re: IMO 2011 Problem 5
This is COMPLETELY wrong.Tahmid Hasan wrote:there is a fun fact,this is a constant function.
do you get it now?
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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Re: IMO 2011 Problem 5
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.
$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