Difference between revisions of "2011 IMO Problems/Problem 5"
m (LaTeX-ify) |
(Added Solution) |
||
Line 1: | Line 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>. | 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== | ||
+ | |||
+ | 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== | ||
+ | |||
+ | 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 <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>. | ||
+ | |||
+ | |||
+ | 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>. |
Revision as of 18:38, 21 May 2012
Let be a function from the set of integers to the set of positive integers. Suppose that, for any two integers
and
, the difference
is divisible by
. Prove that, for all integers
and
with
, the number
is divisible by
.
Solution
Let be a function from the set of integers to the set of positive integers. Suppose that, for any two integers
and
, the difference
is divisible by
. Prove that, for all integers
and
with
, the number
is divisible by
.
Solution
We first note the following facts:
for all
: Since
.
for all
: Since
, we get
from above. This holds for all
, so
for all
.
for all
. Because of the the above observations, we need to show this only for
. When
, this is clearly true. We now use induction, along with the observation that
, so that
.
- If
, then
. We have
which implies that
and therefore
.
From the first three observations, we get the following lemma:
Lemma 1: Suppose , and
. If
divides
, then
.
Proof: Let . Using the second observation above, we get that
. Now, since
, we get that
(from the third observation above), and hence
. Since
as well, and the range of
is positive integers, equation (1) can hold only if
. But
, so
, 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 . So, let
be positive integers, and let
. We now show that if
then
, and hence
.
By the Euclidean algorithm, there exist positive
integers and
such that
. Notice that
divides both
and
. We now have two cases:
Case 1: . In this case, by Lemma 1,
, and hence by the third and fourth observations above,
which implies that
. This immediately implies
by the third observation above, since
.
Case 2: . In this case, by Lemma 1,
, and hence by the third and fourth observations above
. However,
divides both
and
, so by the third observation above, we get that
and
. Thus, using the fact that
, we get
and hence
.