Showing that a greatest common divisor must be 1 or 2 using pigeonhole principle

Question

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?

Answer 1

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.