Difference between revisions of "2011 IMO Problems/Problem 5"

Revision as of 23:13, 10 October 2013

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:

$f(m)|f(0)$ for all $m \in \mathbb{Z}$ : Since $f(m) |( f(m) - f(0))$ .
$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$ .
$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)$ .
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)

@@ Line 3: / Line 3: @@
 ==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==
+'''Solution 2'''
 We first note the following facts:

Page

Toolbox

Search

Difference between revisions of "2011 IMO Problems/Problem 5"

Revision as of 23:13, 10 October 2013

Solution