1
$\begingroup$

I need to prove that for any $S \subset \{1,2,...,2018\}$ with $|S|=673$, it follows that $\exists\,a,b \in S$ such that $gcd(a,b)<3$.

I can see the obvious application of pigeonhole principle here, since $673 \times 3=2019$ and just from the wording of the problem, but unfortunately it's late and I'm having trouble constructing the proof. Any tips?

$\endgroup$
2
  • 1
    $\begingroup$ Hint: $\gcd(n,n+1)=1$ and $\gcd(n,n+2) \in \{1,2\}$ for all $n$. $\endgroup$
    – JavaMan
    Nov 16, 2018 at 11:42
  • $\begingroup$ This turned out to be more helpful, thanks! There are only 672 elements whose difference is greater than or equal to three in the set, which means that by the pigeonhole principle, in any set of cardinality 673 there must be two elements with a difference less than or equal to two. Apply your fact and the problem is solved. $\endgroup$
    – notadoctor
    Dec 8, 2018 at 3:05

1 Answer 1

0
$\begingroup$

Any choice of $k+1$ elements from $kd$ consecutive positive integers where $d\ge2$ contains, by the pigeonhole principle, a pair of elements $b<a$ where $a-b\le d-1$. This pair will have $\gcd(a,b)=\gcd(a-b,b)\le d-1$.

The OP's question is essentially the case when $d=3$ and $k=672$; $1$ and $2$ cannot be chosen since $\gcd(1,n)$ and $\gcd(2,n)$ are less than $3$, but then $673$ elements cannot be chosen from $3,\dots,2018$ that are all at least $3$ apart.

$\endgroup$

You must log in to answer this question.

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