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

(Removed typos) |
|||

(5 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 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 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]] |

## Revision as of 23:14, 10 October 2013

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)