Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Romanian NMO Problems/Grade 7/Problem 4"

m
m
 
Line 4: Line 4:
 
''Marius Gherghu, Slatina''
 
''Marius Gherghu, Slatina''
 
==Solution==
 
==Solution==
−
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.
+
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>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</math> so <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>, then <math>\frac{[n,b]}{n-b} = \frac{bn}{(n-b)^{2}} < \frac{ab}{(a-b)^{2}} = b</math>, contradiction.
+
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==

Latest revision as of 23:27, 7 July 2011

Problem

Let $A$ be a set of positive integers with at least 2 elements. It is given that for any numbers $a>b$, $a,b \in A$ we have $\frac{ [a,b] }{ a- b } \in A$, where by $[a,b]$ we have denoted the least common multiple of $a$ and $b$. Prove that the set $A$ has exactly two elements.

Marius Gherghu, Slatina

Solution

We first show that $A$ is finite; for the sake of contradiction, suppose that $A$ is infinite. Let $a \in A$ be the smallest element of $A$. Let $n \in A$ such that $n > a$ and let $g = GCD(n,a)$. Then $\frac{[n,a]}{n-a} = \frac{na}{g(n-a)} = \frac{a}{g} + \frac{a^{2}}{g(n-a)}$ is an integer for arbitrarily large $n$; but $\frac{a^{2}}{g(n-a)} < \frac{a^{2}}{n-a} < 1$ if $n > a^{2}+a$. Therefore $A$ is finite.

Let $x,y \in A$ with $x > y$; let $g = GCD(x,y)$ and $x_{0} = x/g$ and $y_{0} = y/g$. Then $\frac{[x,y]}{x-y} = \frac{xy}{g(x-y)} = \frac{x_{0}y_{0}}{x_{0}-y_{0}}$. Suppose $x_{0} - y_{0} > 1$ and let $p$ be a prime dividing $x_{0} - y_{0}$; $p$ divides $x_{0}$ if and only if $p$ divides $y_{0}$. But $p$ divides neither because $x_{0}$ and $y_{0}$ are relatively prime. Thus $x_{0} - y_{0} = 1$ and $g = x-y$ and $\frac{xy}{(x-y)^{2}} \in A$ for all $x,y \in A$ such that $x > y$.

Let $b$ be the smallest element and let $a$ be the largest element of $A$. Since $\frac{ab}{(a-b)^{2}} \in A$, we have $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$ and $a-b$ divides $a$ and $b$ so either $0 = (a-b)^{2}-b$ or $(a-b)^{2}-b = a-b$ and $(a-b)^{2}$ equals $a$ or $b$. Suppose there exists some $n \in A$ such that $b < n < a$. If $(a-b)^{2} = b$, then $\frac{[n,a]}{a-n} = \frac{an}{(a-n)^{2}} > \frac{ab}{(a-b)^{2}} = a$, contradiction. If $(a-b)^{2} = a$, we can without loss of generality assume that $n$ is the second largest element of $A$. Then $\frac{[n,a]}{a-n} = \frac{an}{(a-n)^{2}} > \frac{an}{(a-b)^{2}} = n$ so $\frac{an}{(a-n)^{2}} = a \implies n = (a-n)^{2} \implies (a-b)^{2} = a = (a-n)^{2} + (a-n)$ and $(a-b)^{2} - (a-n)^{2} = a-n \implies (n-b)(a-b+a-n) = a-n$ which is a contradiction since $a-b,n-b > 0$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Romanian_NMO_Problems/Grade_7/Problem_4&oldid=40298"