Largest value of $n$ such that the complementary set of any $n$-element subset contains at least two elements that are coprime

Question

What is the largest value of $n$ such that the complementary set of any subset with $n$ elements of {1, 2, ..., 1989} contains at least two elements that are coprime? I am looking for the most general solution. For the sake of context: any mathematical methods can be used to provide a solution to the problem, so long as the solution is the most general.

Answer 1

Let $S$ be a finite set of consecutive integers, $|S|\ge2$. Let $D=\{x\in S:x\text{ is odd}\}$ and $E=\{x\in S:x\text{ is even}\}$.

Claim. $|D|-1$ is the largest number $n\le|S|$ such that, for any $n$-element set $X\subseteq S$, the complementary set $S\setminus X$ contains two coprime elements.

I, Suppose $n=|D|-1$. Consider any set $X\subseteq S$ with $|X|=n=|D|-1$, and let $Y=S\setminus X$, so that $|Y|=|E|+1\ge2$. It is easy to see that $Y$ contains two consecutive integers unless $Y=D$. In either case, $Y$ contains two coprime elements; either two consecutive integers or else two consecutive odd numbers.

II. Suppose $|D|\le n\le|S|$. Then there is an $n$-element set $X$ such that $D\subseteq X\subseteq S$. Since all elements of $S\setminus X$ are even numbers, no two of them are coprime.