0

Sorry the title isn't complete, but my title was over 150 characters, so here is the question:

What is the least possible value of $n$ in a set of the form ${1, 2, ..., n}$ such that it can be partitioned into $2$ subsets in which one must have two elements $a$ and $b$ so that $ab$ is divisible by $a+b$.

This question is probably easiest done by guess and check and just grinding through until you get it, but I wanted to know if there was a more quick and safe way to do it. Thanks!

Peter Taylor
  • 13,425
user406996
  • 663
  • 1
  • 5
  • 14
  • What are your thoughts so far? –  May 14 '17 at 19:18
  • I don't know how to solve it other than guess and check, which would take a long time. – user406996 May 14 '17 at 19:18
  • Note that $\frac{ab}{a+b}=a-\frac{a^2}{a+b}=b-\frac{b^2}{a+b}$, so if $ab$ is divisible by $a+b$, then $a^2$ and $b^2$ are as well. I'm not sure if that helps you narrow down the possibilities or not. Also, when you say "two elements $a$ and $b$" do you mean they must be distinct? – kccu May 14 '17 at 19:20
  • Is it same the opposite way around, though? – user406996 May 14 '17 at 19:21
  • @user406996 Yes, because $\frac{a^2}{a+b}= a-\frac{ab}{a+b}$ and $\frac{b^2}{a+b}=b-\frac{ab}{a+b}$. So $ab$ is divisible by $a+b$ if and only if $a^2$ is divisible by $a+b$, if and only if $b^2$ is divisible by $a+b$. – kccu May 14 '17 at 19:28
  • I'm not sure how much that helps, though >.< – user406996 May 14 '17 at 19:31
  • Another question: you say "2 subsets in which one must have two elements..." Do you mean each one? Or at least one? – kccu May 14 '17 at 19:38
  • the subsets can have any amount of elements, but one of them needs at least 2 terms. – user406996 May 14 '17 at 19:39
  • I've just retagged this from [tag:partition] to [tag:set-partition] because it talks about partitioning a set. But the accepted answer isn't answering what I thought the question was, and I'm not sure that the partition couldn't be removed entirely from the question. Is "such that it can be partitioned into 2 subsets in which one must have..." intended to mean that for every partition of $[1,n]$ into $S$ and $T$ one of $S$ or $T$ has the desired divisibility property? If not, surely the partition is a red herring? The accepted answer seems to partition into $[1, n]$ and $\emptyset$. – Peter Taylor Nov 28 '17 at 09:07
  • If you meant the other, $24, 40, 10, 15, 30, 6, 12, 24$ is an odd cycle and hence not bipartite. – Peter Taylor Nov 28 '17 at 17:32

1 Answers1

1

$x+y~|~ xy\Rightarrow \exists k~~s.t. (x+y)k=xy~~or, ~~(x-k)(y-k)=k^2$. Now we want $x\neq y$. So wlog assume $x<y$, then $x-k<k<y-k$ such that $(x-k)(y-k)=k^2$. $k$ cannot be $1$, because this leads to $x=y=2$. If $k=2$, then $k^2=4=1\times4=(3-2)\times(6-2)$. So smallest such $n$ for which $\{1,\cdots, n\}$ contains two numbers, such that their product is divisible by their sum, is $6$.

QED
  • 12,644
  • I understand your logic until around k^2 can't be the square of a prime. I got 12 through bash, so I accepted your answer. – user406996 May 14 '17 at 19:42
  • 1
    This is not right. If $k^2=2^2=4$ we can have $x=3$ and $y=6$. Then $(x-k)(y-k)=(3-2)(6-2)=1\cdot 4 = 4$. $k$ can be the square of a prime, but then we must have $x-k=1$ and $y-k=k^2$. – kccu May 14 '17 at 19:46
  • We cannot have $k=1$, or else $x-k=y-k=1$, so $x=y=2$. Thus $n=6$ must in fact be the smallest. – kccu May 14 '17 at 19:48
  • @kccu: ${1,2,\cdots,6}$ does not contain two numbers such that their sum divides their product. Why do you think $n=6$ is the smallest? – QED May 14 '17 at 19:58
  • $3\cdot 6=18$ is divisible by $3+6=9$. – kccu May 14 '17 at 20:08
  • Oh thanks, why did i miss that! But then what is wrong with my proof – QED May 14 '17 at 20:10
  • 1
    Exactly what OP pointed out: $k^2$ can be the square of an integer. The smallest one is $k^2=1$, but as I pointed out that leads to $x=y=2$, which is no good. The next smallest is $k^2=4$, which leads to $x=3$, $y=6$. – kccu May 14 '17 at 20:11
  • Yes of course. Edited my answer likewise. – QED May 14 '17 at 20:19