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"

(Created page with "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 − ...")
 
(→‎See Also)
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
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) ≤ f(n), the number f(n) is divisible by f(m).
+
Let <math>f</math> be a function from the set of integers to the set of positive integers. Suppose that, for any two integers <math>m</math> and <math>n</math>, the difference <math>f(m) - f(n)</math> is divisible by <math>f(m - n)</math>. Prove that, for all integers <math>m</math> and <math>n</math> with <math>f(m) \leq f(n)</math>, the number <math>f(n)</math> is divisible by <math>f(m)</math>.
 +
 
 +
==Solution==
 +
 
 +
'''Solution 1'''
 +
Let <math>f</math> be a function from the set of integers to the set of positive integers. Suppose that, for any two integers <math>m</math> and <math>n</math>, the difference <math>f(m) - f(n)</math> is divisible by <math>f(m - n)</math>. Prove that, for all integers <math>m</math> and <math>n</math> with <math>f(m) \leq f(n)</math>, the number <math>f(n)</math> is divisible by <math>f(m)</math>.
 +
 
 +
'''Solution 2'''
 +
 
 +
We first note the following facts:
 +
 
 +
# <math>f(m)|f(0)</math> for all <math>m \in \mathbb{Z}</math>:  Since <math>f(m) |( f(m) - f(0))</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>.
 +
# 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).
 +
 
 +
 
 +
From the first three observations, we get the following lemma:
 +
 
 +
'''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.
 +
 
 +
 
 +
We can now complete the proof.  Notice that because of the first and
 +
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 =
 +
{\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>.
 +
 
 +
By the Euclidean algorithm, there exist positive
 +
integers <math>x</math> and <math>y</math> such that <math>mx = ny + g</math>.  Notice that <math>g = mx -
 +
ny</math> divides both <math>mx</math> and <math>ny</math>.  We now have two cases:
 +
 
 +
 
 +
''Case 1: <math>f(mx) \leq f(ny)</math>.'' In this case, by Lemma 1, <math>f(mx) |
 +
f(ny)</math>, and hence by the third and fourth observations above, <math>f(m) |
 +
f(mx - g)</math> which implies that <math>f(m) | f(g)</math>.  This immediately implies <math>f(m) | f(n)</math> by the third observation above, since <math>g | n</math>.
 +
 
 +
''Case 2: <math>f(mx) > f(ny)</math>.'' In this case, by Lemma 1, <math>f(ny) |
 +
f(mx)</math>, and hence by the third and fourth observations above <math>f(n) |
 +
f(g)</math>.  However, <math>g</math> divides both <math>m</math> and <math>n</math>, so by the third observation above, we get that <math>f(g)|f(n)</math> and <math>f(g)|f(m)</math>.  Thus, using the fact that <math>f(m) \leq f(n)</math>, we get <math>f(g) = f(m) = g(n)</math> and hence <math>f(m) | f(n)</math>.
 +
 
 +
--[[User:Mahamaya|<font color="#FF00FF">Maha</font><font color="#E0B0FF">maya</font>]] 20:05, 21 May 2012 (EDT)
 +
 
 +
==See Also==
 +
*[[2011 IMO Problems]]
 +
 
 +
{{IMO box|year=2011|num-b=4|num-a=6}}

Latest revision as of 00:21, 19 November 2023

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

Solution 1 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 2

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

--Mahamaya 20:05, 21 May 2012 (EDT)

See Also

2011 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_IMO_Problems/Problem_5&oldid=204548"