What is the max value of $|S|$ where $S$ is a set with the following conditions?

Question

1. $S$ is a subset of the first 1000 integers.
2. No two elements of $S$ differ by 4 or 7. I have tried dividing the set of integers upto 1000 into subsets of 4 and 7 integers and tried to include into $S$ the numbers common to them. However this approach lead nowhere. Please suggest a solution.

Answer 1

First consider how many numbers we can select from $\{1, 2, \ldots, 11\}$, let's take $1$, rules out $5, 8$. Next we can take $2, 4, 7, 10$. Since, $1000 = 11\times90+10$, we definitely get $5\times90=450$ numbers from $\{1,\ldots, 990\}$, now the remaining set is of size 10, and you can get $5$ numbers out of a set of size $10$, as we saw above.

So largest set with above property should be $455$.

To prove this more formally, you can take any optimal set $A$, and convert it into the set we constructed greedily.

Let $i$ be least positive integer such that the sets differ after this point. Say $i \not \in A$ but it is in constructed set. This means at least one of $i+4, i+7$ must be in $A$.

You can consider cases, say $i+4 \in A$, If $i+7 \not \in A$ then $A \setminus \{i+4\} \cup \{i\}$ is of same size, If $i+7 \in A$ then $i+3 \not \in A$, thus $A\setminus\{i+4, i+7\} \cup \{i, i+3\}$ (assuming $i+10 \not\in A$) and so on. Thus other cases can be handled in very similar manner.

In case $i \in A$, not in constructed set. Then at least one of $i-4, i-7$ must be in constructed set. which means at least one of $i-4$ or $i-7$ is in $A$, a contradiction.