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"

(Added Solution)
(Removed typos)
Line 12: Line 12:
 
# <math>f(m) = f(-m)</math> for all <math>m \in \mathbb{Z}</math>: Since <math>f(m) | (f(0) - f(-m))</math>, we get <math>f(m) | f(-m)</math> from above.  This holds for all <math>m</math>, so <math>f(m) = f(-m)</math> for all <math>m</math>.
 
# <math>f(m) = f(-m)</math> for all <math>m \in \mathbb{Z}</math>: Since <math>f(m) | (f(0) - f(-m))</math>, we get <math>f(m) | f(-m)</math> from above.  This holds for all <math>m</math>, so <math>f(m) = f(-m)</math> for all <math>m</math>.
 
# <math>f(m)|f(km)</math> for all <math>k \in \mathbb{Z}</math>.  Because of the the above observations, we need to show this only for <math>k > 0</math>.  When <math>k = 1</math>, this is clearly true.  We now use induction, along with the observation that <math>f(m)|(f((k+1)m) - f(km))</math>, so that <math>f(m)|f(km) \implies f(m)|f((k+1)m)</math>.
 
# <math>f(m)|f(km)</math> for all <math>k \in \mathbb{Z}</math>.  Because of the the above observations, we need to show this only for <math>k > 0</math>.  When <math>k = 1</math>, this is clearly true.  We now use induction, along with the observation that <math>f(m)|(f((k+1)m) - f(km))</math>, so that <math>f(m)|f(km) \implies f(m)|f((k+1)m)</math>.
−
# If <math>f(a) | f(ax + b)</math>, then <math>f(a) | f(b)</math>.  We have <math>f(ax)|)f(ax+b)-f(b))</math> which implies that <math>f(a)|(f(ax + b) - f(b))</math> and therefore <math>f(a) | f(b)</math>.  
+
# If <math>f(a) | f(ax + b)</math>, then <math>f(a) | f(b)</math>.  We have from the hypotheses that <math>f(ax)|(f(ax+b)-f(b))</math> which implies that <math>f(a)|(f(ax + b) - f(b))</math> and therefore <math>f(a) | f(b)</math> (here we used the last observation).
  
  
Line 25: Line 25:
 
second observations above, we can assume without loss of generality
 
second observations above, we can assume without loss of generality
 
that <math>m, n > 0</math>.  So, let <math>m,n</math> be positive integers, and let <math>g =
 
that <math>m, n > 0</math>.  So, let <math>m,n</math> be positive integers, and let <math>g =
−
{\rm gcd n, m}</math>.  We now show that if <math>f(m) \leq f(n)</math> then
+
{\rm gcd (n, m)}</math>.  We now show that if <math>f(m) \leq f(n)</math> then
 
<math>f(m)|f(g)</math>, and hence <math>f(m) | f(n)</math>.
 
<math>f(m)|f(g)</math>, and hence <math>f(m) | f(n)</math>.
  

Revision as of 17:39, 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=47086"