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 "2011 IMO Problems/Problem 5"

(Removed typos)
m (Typos)
Line 19: Line 19:
 
'''Lemma 1''':  Suppose <math>m \neq n</math>, and <math>f(m) \leq f(n)</math>.  If <math>|n-m|</math> divides <math>n</math>, then <math>f(m) | f(n)</math>.   
 
'''Lemma 1''':  Suppose <math>m \neq n</math>, and <math>f(m) \leq f(n)</math>.  If <math>|n-m|</math> divides <math>n</math>, then <math>f(m) | f(n)</math>.   
  
−
'''Proof''': Let <math>d = |n-m|</math>. Using the second observation above, we get that <cmath>f(n)|(f(d) - f(m))\;\;\;\;\;\;(1)</cmath>. Now, since <math>d|n</math>, we get that <math>f(d) | f(n)</math> (from the third observation above), and hence <math>f(d) \leq f(n)</math>.  Since <math>f(m) \leq f(n)</math> as well, and the range of <math>f</math> is positive integers, equation (1) can hold only if <math>f(m) = f(d)</math>.  But <math>f(d) | f(n)</math>, so <math>f(m) | f(n)</math>, as required.
+
'''Proof''': Let <math>d = |n-m|</math>. Using the second observation above, we get that <cmath>f(n)|(f(d) - f(m)).\;\;\;\;\;\;(1)</cmath>  Now, since <math>d|n</math>, we get that <math>f(d) | f(n)</math> (from the third observation above), and hence <math>f(d) \leq f(n)</math>.  Since <math>f(m) \leq f(n)</math> as well, and the range of <math>f</math> is positive integers, equation (1) can hold only if <math>f(m) = f(d)</math>.  But <math>f(d) | f(n)</math>, so <math>f(m) | f(n)</math>, as required.
  
  

Revision as of 17:40, 21 May 2012

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)$.

Solution

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)$.

Solution

We first note the following facts:

  1. $f(m)|f(0)$ for all $m \in \mathbb{Z}$: Since $f(m) |( f(m) - f(0))$.
  2. $f(m) = f(-m)$ for all $m \in \mathbb{Z}$: Since $f(m) | (f(0) - f(-m))$, we get $f(m) | f(-m)$ from above. This holds for all $m$, so $f(m) = f(-m)$ for all $m$.
  3. $f(m)|f(km)$ for all $k \in \mathbb{Z}$. Because of the the above observations, we need to show this only for $k > 0$. When $k = 1$, this is clearly true. We now use induction, along with the observation that $f(m)|(f((k+1)m) - f(km))$, so that $f(m)|f(km) \implies f(m)|f((k+1)m)$.
  4. If $f(a) | f(ax + b)$, then $f(a) | f(b)$. We have from the hypotheses that $f(ax)|(f(ax+b)-f(b))$ which implies that $f(a)|(f(ax + b) - f(b))$ and therefore $f(a) | f(b)$ (here we used the last observation).


From the first three observations, we get the following lemma:

Lemma 1: Suppose $m \neq n$, and $f(m) \leq f(n)$. If $|n-m|$ divides $n$, then $f(m) | f(n)$.

Proof: Let $d = |n-m|$. Using the second observation above, we get that \[f(n)|(f(d) - f(m)).\;\;\;\;\;\;(1)\] Now, since $d|n$, we get that $f(d) | f(n)$ (from the third observation above), and hence $f(d) \leq f(n)$. Since $f(m) \leq f(n)$ as well, and the range of $f$ is positive integers, equation (1) can hold only if $f(m) = f(d)$. But $f(d) | f(n)$, so $f(m) | f(n)$, as required.


We can now complete the proof. Notice that because of the first and second observations above, we can assume without loss of generality that $m, n > 0$. So, let $m,n$ be positive integers, and let $g = {\rm gcd (n, m)}$. We now show that if $f(m) \leq f(n)$ then $f(m)|f(g)$, and hence $f(m) | f(n)$.

By the Euclidean algorithm, there exist positive integers $x$ and $y$ such that $mx = ny + g$. Notice that $g = mx - ny$ divides both $mx$ and $ny$. We now have two cases:


Case 1: $f(mx) \leq f(ny)$. In this case, by Lemma 1, $f(mx) | f(ny)$, and hence by the third and fourth observations above, $f(m) | f(mx - g)$ which implies that $f(m) | f(g)$. This immediately implies $f(m) | f(n)$ by the third observation above, since $g | n$.

Case 2: $f(mx) > f(ny)$. In this case, by Lemma 1, $f(ny) | f(mx)$, and hence by the third and fourth observations above $f(n) | f(g)$. However, $g$ divides both $m$ and $n$, so by the third observation above, we get that $f(g)|f(n)$ and $f(g)|f(m)$. Thus, using the fact that $f(m) \leq f(n)$, we get $f(g) = f(m) = g(n)$ and hence $f(m) | f(n)$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_5&oldid=47087"