Find all subsets $A$ of $\left\{ 1, 2, 3, 4, \ldots \right\}$, with $|A| \geq 2$, such that for all $x,y \in A, \, x \neq y$, we have that $\frac{x+y}{\gcd (x,y)}\in A$. Dan Schwarz
Problem
Source: Romanian TST 2 2007, Problem 3
Tags: induction, number theory proposed, number theory
15.04.2007 14:15
$A=\{2\}$http://www.mathlinks.ro/Forum/viewtopic.php?p=474988#p474988
15.04.2007 16:20
But this one it says $x\neq y$. Come on, Romania won't copy problems
15.04.2007 16:38
http://www.mathlinks.ro/Forum/viewtopic.php?t=132713
15.04.2007 17:45
May you tell me where it's mentioned in this problem that $A$ is finite? And, of course, we must have that $x \neq y$.
15.04.2007 17:54
Here's an outline of a proof: consider two smallest elements of the set and call them $x \leq y$. There are to cases: one easy to tackle is $(x,y)>1$ and another is $(x,y)=1$. To deal with second one see that $kx+y$ and $ky+x \in A$ hence $yx+x \in A$ and $\frac{(yx+y)+y)}{y}=x+2 \in A$ so either $y=x+1$ or $y=x+2$. See that $xy+x+y \in A$, then $2xy+x^{2}+y^{2}+kx+ky \in A$ (just by adding $x$ or $y$ one by one) hence $\frac{(x+y)(x+y+k)+(x+y)}{x+y}=x+y+k+1 \in A$ and taking sufficient k we get $3 \in A$. Now there are some cases to check and we get generally that $\mathbb{N}, \mathbb{N}-\{1\}, \mathbb{N}-\{1,2\}$ works. Also from the first case $(x,y)>1$ we get $A=\mathbb{N}$
15.04.2007 23:21
actually, there is another solution, more precisely, a family of finite solutions. when $\gcd(a,b)>1$ ($a<b$ are the two smallest elements of $A$), note that $\frac{a+b}{\gcd(a,b)}<b$, thus it must be equal to $a$. from here it`s not very hard to see that $a=d$, $b=d(d-1)$. now, let $c$ be the third element of $A$. if $\gcd(b,c)=1$ or $\gcd(a,c)=1$, then it is the same as the case when $\gcd(a,b)=1$ (with some work it can be proved that $3,4\in A$, and from there it`s easy). if $\gcd(a,c)>1$ and $\gcd(b,c)>1$, note that $\frac{a+c}{\gcd(a,c)}$ and $\frac{b+c}{\gcd(b,c)}$ are smaller than $c$, thus they must be $a$ and $b$. checking both cases leads to contradiction. thus, the solutions are that above, and sets of the form $\{d,d(d-1)\}$, where $d\geq 3$.
16.04.2007 07:37
1. $\frac{x+x}{gcd(x,x)}=2\in A$. 2. If all terms A even and x is minimal term, greater, than 2 we get $2<\frac{x}{2}+1<x\in A$ give contradition. Therefore exist odd terms. If x odd term, then $\frac{x+2}{gcd(x,2)}=x+2\in A$, therefore all odd primes greater N in A. Let $x$ odd term, then $x<3x\in A$, therefore $\frac{x+3x}{gcd(x,3x)}=4\in A$ and $\frac{2+4}{gcd(2,4)}=3\in A$, therefore all odd numbers greater 1 in A. 3. All even numbers in A, because if m even, then odd terms $x, (m-1)x\in A$, therefore $\frac{x+(m-1)x}{gcd(x,(m-1)x)}=m\in A.$ It mean $A=N$ or $A=N/\{1\}.$
16.04.2007 09:03
Rust, $x \not =y$ is one of the conditions
16.04.2007 10:50
Ok! 1. If exist to terms $x,y\in A$, suth that $(x,y)=1$, then $x,y+x\in A, (x,y+x)=1$, therefore (by induction $x,y+nx\in A, (x,y+nx)=1, \ \forall n\in N$. It give $y+yx\in A\Longrightarrow \frac{y+y+yx}{(y,y+yx)}=x+2\in A.$ Because $(x,y)=1$ one of them odd, let it be x. It give all odd numbers greater, than x in A. Therefore $x,(2n-1)x\in A\Longrightarrow 2n\in A \ \forall n\ge 2.$ From $4,8\in A\Longrightarrow 3\in A$. In mean, that we proof if exist x,y in A, suth that (x,y)=1, then $n\in A \ \forall n>2$. 2. Let x is minimal term in A and y is term, suth that $(x,y)=d$ - minimal divisor. Then $x=ad, y=bd, (a,b)=1,a+b\in A$. We have $(x,a+b)|(x,ad+bd)=(x,x+y)=(x,y)=d$. Because d is minimal mean for (x,y) we get $(x,a+b)=d$ and $a+b<y$. Because we have finite numbers in interval (x,y) it give contradition with $(x,z)\ge d \ \forall z\in A.$ It mean exist y, suth that $(x,y)=1$, therefore $3\le n\in A \ \forall n\in N$.
16.04.2007 13:28
as i said above, the case when there exists no pair $a,b$ with $\gcd(a,b)=1$ leads to a solution with $|A|=2$, that is, the family of sets of the form $\{d,d(d-1)\}$, with $d\geq 3$. here is my proof : take $a<b$ the smallest elements of $A$, and assume $d=\gcd(a,b)>1$. let $a=dx$, $b=dy$. from the hypothesis, $x+y\in A$. however, $x+y=\frac{a+b}{d}\leq \frac{a+b}{2}<b$, thus $x+y=a$, that is $x+y=dx$, or $y=x(d-1)$. this means $x|y$, but since $\gcd(x,y)=1$, it follows that $x=1$ and $y=d-1$. thus, $a=d$ and $b=d(d-1)$, leading to a solution. now, i assume that $|A|>2$. take $c$ the third element of $A$ (that is, $a<b<c$ are the smallest elements of $A$). if $\gcd(a,c)=1$ or $\gcd(b,c)=1$, then this case is solved (by methods above). so let`s assume $\gcd(a,c)>1$, $\gcd(b,c)>1$. using the same idea as above, the numbers $\frac{a+c}{\gcd(a,c)}$ and $\frac{b+c}{\gcd(b,c)}$ are in $A$, but they are both smaller than $c$, so they must be $a$ and $b$. if $\frac{a+c}{\gcd(a,c)}=a$, it follows that $c=b$, contradiction. now, let $a=eu$, $c=ev$, with $e=\gcd(a,c)$. from the fact that $u+v=b$, it follows that $v=b-u=a(a-1)-u=eu(a-1)-u=u(e(a-1)-1)$. so again $u=1$, $e=d$, $v=d(d-1)-1$. thus, $\gcd(b,c)=\gcd(a,c)=d$, and $b=\frac{a+c}{\gcd(a,c)}<\frac{b+c}{\gcd(b,c)}<c$, so i found an element of $A$ between $b$ and $c$, contradiction. thus, if $|A|\geq 3$, there exists two coprime elements of $A$.
01.01.2008 07:18
Megus wrote: then $ 2xy + x^{2} + y^{2} + kx + ky \in A$ (just by adding $ x$ or $ y$ one by one) Hmm... are you sure you can get this by adding $ x$ or $ y$ one by one?
16.01.2008 08:35
Can anybody explain?
29.12.2018 16:57
I've proved to finite sets the following statement: If S= {a_1 < a_2 < ... < a_n} satisfies these conditions, then a_k = a_1(a_k -1) for all k which means that the sequence is established by the smallest term. Then it's not hard to check that the 3 smallest elements cause an absurd. Then it must have at maximum 2 elements which leads us to the solution: {x, x(x-1)}