1
$\begingroup$

For $A=\{1,2,\cdots ,2012\}$ , find the largest positive integer $(k>2)$ such that it is possible to choose $k$ elements in $A$ whose sum of any two distinct numbers among the k chosen numbers is not divisible by their difference.

I think it has something to do with divisibility by $3$. $2$ different numbers that divide by $3$ leave a remainder of $2$ whose sum is not divisible by the difference.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Define $B$ as a subset of $A$ such that the sum of any two numbers in $B$ is not divisible by their difference.

Observe, we can choose only one of the three consecutive numbers, $x$, $x+1$ and $x+2$ to be elements of $B$. Therefore, $k=|B|\le \left\lceil \dfrac{2012}{3}\right\rceil=671$. It remains to show that such a set $B$ with $671$ elements exists. The following construction proves that $k_{\max}=671$. $$B=\{1,4,7,\cdots,2011\}\implies |B|=671$$

$\endgroup$
2
  • $\begingroup$ Why we can chose only one of the three consecutive numbers $x,x+1, x+2$? Can you explain fo me more details? $\endgroup$
    – Hung nguyen
    Commented Jun 15, 2021 at 5:28
  • 2
    $\begingroup$ Try choosing two of the three consecutive numbers. Does it satisfy the conditions ?(check their sum and difference). Hope it helps :) $\endgroup$
    – Sathvik
    Commented Jun 15, 2021 at 5:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .