3
$\begingroup$

Prove that for any integer $n>1$, there exists a set of $n$ positive integers such that, for any two numbers among them (say $a$ and $b$), $a-b$ divides $a+b$

I have come up with three strategies to tackle this problem:

(i) Try to construct a set satisfying the conditions

(ii) Induction

(iii) Try to prove it by contradiction. (Which is, I think very difficult to do so)

I have tried smaller examples hoping to find a pattern. Tried arithmetic, geometric series, but no luck. It is very hard to even come up with an example for $n=5$. We can make some simple observations like $(n,n+1)$ and $(n,n+2)$ always work. But the thing with this problem, that is making it difficult, is the rule should be followed by every two numbers in the set.

Induction definitely fails, fix any number $a$, then condition $a-x|a+x$ can also be written as $a-x|2a$. Which means there are only finitely many values of $x$ which satisfies the condition. So, we can't rely on induction

I am not sure, how can we go about using (ii)? Or is there any other method?

$\endgroup$
2
  • 1
    $\begingroup$ Do you mean that you have come up with an example for $n=5$? If not, what's the best $n$ for which you have an example? $\endgroup$ Nov 6 '20 at 5:18
  • $\begingroup$ I have example for 4. I want to find for any $n$ $\endgroup$ Nov 6 '20 at 5:22
4
$\begingroup$

It's too early to say that induction fails just because the simplest thing to try doesn't work: adding a new element to an existing set.

The next thing to try is: given an $n$-element set $S$ for which this property holds, can we turn it into a different $n$-element set for which it will be easier to add a new element?

I thought of two things that we can do to change $S$:

  • We can multiply every element of $S$ by a fixed factor $k$. This doesn't break divisibility, but also doesn't seem super useful.
  • We can add $k$ to every element of $S$, provided that $a-b \mid 2k$ for every pair $a,b \in S$. There are infinitely many such $k$; for instance, the LCM of the pairwise differences.

Okay, now if we can shift $S$ over, is there a convenient element we can try adding to $S$?

Adding the element $0$ always works: the divisibility condition is that $a - 0 \mid a+0$. Of course, $0$ is not a positive integer, but we can shift the elements over to make everything positive.

So now we have a method to increase the size of any set $S$ with this property by $1$:

  1. Let $S' = S \cup \{0\}$.
  2. Let $k$ be the LCM of all pairwise differences in $S'$, and let $S'' = S'+k$.

The result $S''$ after the second step is the bigger set we wanted.


In principle, once we have an inductive proof, we can try to understand the construction it gives, and simplify it to a direct argument. But in this case, starting with the $2$-element set $\{1,2\}$, I don't see a nice pattern for what happens later:

  • $\{1,2\}$ becomes $\{1,2,3\}$
  • $\{1,2,3\}$ becomes $\{6,7,8,9\}$
  • $\{6,7,8,9\}$ becomes $\{504, 510, 511, 512, 513\}$
  • $\{504, 510, 511, 512, 513\}$ becomes $\{11408463360, 11408463864, 11408463870, 11408463871, 11408463872, 11408463873\}$
  • I decided not to continue.
$\endgroup$
2
  • 2
    $\begingroup$ Wow! I never thought it could be done like this! I thought, it is useless to think about $0$ and ignored it but in reality, it played a crucial role in providing the final proof. Thanks for your enlightenment. $\endgroup$ Nov 6 '20 at 5:45
  • 2
    $\begingroup$ @MathematicalCuriosity The idea of "let's relax restrictions" can be extremely helpful for such construction problems. E.g. If we want to prove a certain square exists, first we find some rectangles that satisfy the conditions, then show that the length = breadth. $\endgroup$
    – Calvin Lin
    Nov 7 '20 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.