Difference between revisions of "2006 Romanian NMO Problems/Grade 7/Problem 4"
m |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 4: | Line 4: | ||
''Marius Gherghu, Slatina'' | ''Marius Gherghu, Slatina'' | ||
==Solution== | ==Solution== | ||
+ | We first show that <math>A</math> is finite; for the sake of contradiction, suppose that <math>A</math> is infinite. Let <math>a \in A</math> be the smallest element of <math>A</math>. Let <math>n \in A</math> such that <math>n > a</math> and let <math>g = GCD(n,a)</math>. Then <math>\frac{[n,a]}{n-a} = \frac{na}{g(n-a)} = \frac{a}{g} + \frac{a^{2}}{g(n-a)}</math> is an integer for arbitrarily large <math>n</math>; but <math>\frac{a^{2}}{g(n-a)} < \frac{a^{2}}{n-a} < 1</math> if <math>n > a^{2}+a</math>. Therefore <math>A</math> is finite. | ||
+ | |||
+ | Let <math>x,y \in A</math> with <math>x > y</math>; let <math>g = GCD(x,y)</math> and <math>x_{0} = x/g</math> and <math>y_{0} = y/g</math>. Then <math>\frac{[x,y]}{x-y} = \frac{xy}{g(x-y)} = \frac{x_{0}y_{0}}{x_{0}-y_{0}}</math>. Suppose <math>x_{0} - y_{0} > 1</math> and let <math>p</math> be a prime dividing <math>x_{0} - y_{0}</math>; <math>p</math> divides <math>x_{0}</math> if and only if <math>p</math> divides <math>y_{0}</math>. But <math>p</math> divides neither because <math>x_{0}</math> and <math>y_{0}</math> are relatively prime. Thus <math>x_{0} - y_{0} = 1</math> and <math>g = x-y</math> and <math>\frac{xy}{(x-y)^{2}} \in A</math> for all <math>x,y \in A</math> such that <math>x > y</math>. | ||
+ | |||
+ | Let <math>b</math> be the smallest element and let <math>a</math> be the largest element of <math>A</math>. Since <math>\frac{ab}{(a-b)^{2}} \in A</math>, we have <math>b \le \frac{ab}{(a-b)^{2}} \le a \implies b \le (a-b)^{2} \le a \implies 0 \le (a-b)^{2}-b \le a-b</math> and <math>a-b</math> divides <math>a</math> and <math>b</math> so either <math>0 = (a-b)^{2}-b</math> or <math>(a-b)^{2}-b = a-b</math> and <math>(a-b)^{2}</math> equals <math>a</math> or <math>b</math>. Suppose there exists some <math>n \in A</math> such that <math>b < n < a</math>. If <math>(a-b)^{2} = b</math>, then <math>\frac{[n,a]}{a-n} = \frac{an}{(a-n)^{2}} > \frac{ab}{(a-b)^{2}} = a</math>, contradiction. If <math>(a-b)^{2} = a</math>, we can without loss of generality assume that <math>n</math> is the second largest element of <math>A</math>. Then <math>\frac{[n,a]}{a-n} = \frac{an}{(a-n)^{2}} > \frac{an}{(a-b)^{2}} = n</math> so <math>\frac{an}{(a-n)^{2}} = a \implies n = (a-n)^{2} \implies (a-b)^{2} = a = (a-n)^{2} + (a-n)</math> and <math>(a-b)^{2} - (a-n)^{2} = a-n \implies (n-b)(a-b+a-n) = a-n</math> which is a contradiction since <math>a-b,n-b > 0</math>. | ||
+ | |||
==See also== | ==See also== | ||
*[[2006 Romanian NMO Problems]] | *[[2006 Romanian NMO Problems]] | ||
+ | |||
+ | [[Category:Olympiad Combinatorics Problems]] | ||
+ | [[Category:Olympiad Number Theory Problems]] |
Latest revision as of 23:27, 7 July 2011
Problem
Let be a set of positive integers with at least 2 elements. It is given that for any numbers
,
we have
, where by
we have denoted the least common multiple of
and
. Prove that the set
has exactly two elements.
Marius Gherghu, Slatina
Solution
We first show that is finite; for the sake of contradiction, suppose that
is infinite. Let
be the smallest element of
. Let
such that
and let
. Then
is an integer for arbitrarily large
; but
if
. Therefore
is finite.
Let with
; let
and
and
. Then
. Suppose
and let
be a prime dividing
;
divides
if and only if
divides
. But
divides neither because
and
are relatively prime. Thus
and
and
for all
such that
.
Let be the smallest element and let
be the largest element of
. Since
, we have
and
divides
and
so either
or
and
equals
or
. Suppose there exists some
such that
. If
, then
, contradiction. If
, we can without loss of generality assume that
is the second largest element of
. Then
so
and
which is a contradiction since
.