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

2006 Romanian NMO Problems/Grade 7/Problem 4

Revision as of 22:27, 7 July 2011 by Minsoens (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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"