Difference between revisions of "2011 IMO Problems/Problem 5"
(Added Solution) |
(→See Also) |
||
(7 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
==Solution== | ==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>. | 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: | We first note the following facts: | ||
Line 12: | Line 13: | ||
# <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)| | + | # 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 19: | Line 20: | ||
'''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> | + | '''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. |
Line 25: | Line 26: | ||
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>. | ||
Line 40: | Line 41: | ||
f(mx)</math>, and hence by the third and fourth observations above <math>f(n) | | 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>. | 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 01:21, 19 November 2023
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
Solution 1
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 2
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 from the hypotheses that
which implies that
and therefore
(here we used the last observation).
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
.
--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 |