Let $S$ be a subset of $\{1, 2, \dots , 2019\}$ such that no two members of $S$ differ by 1, 2 or 9. What is the upper bound of the size of $S$?

Question

My solution is that you can take 4 integers from any 12 consecutive integers, and since $2019 = 168*12+3$ you'll have a total of $168*4+1 = 673$ integers in $S$. I have no way to check if my solution is correct so any kind of help will be appreciated.

Answer 1

Your answer has an issue where the numbers in one set of 12 consecutive numbers might not be compatible with the numbers from the next set of 12 consecutive numbers. For example, using the initial sequence of Farseed AF's answer, $\{1, 4, 7, 11\}$, you will no longer be able to choose $13$ from the $13$ to $24$. In fact, if you go further, between $25$ to $36$, you will not be able to find $4$ numbers.

To see another way that Fareed AF's answer is optimal, let's phrase the problem this way. Without loss of generality, let the set be ordered from smallest to largest and starting with 1. Then we can think of $S = \{s_1,s_2,\ldots,s_n\}$ as a sequences of differences $D = \{d_1,d_2,\ldots,d_{n-1}\}$ where $d_i = s_{i+1} - s_i$. And the restriction then becomes no consecutive sums of $d_i$ can be $1$, $2$ or $9$. To maximize the sequence length, we minimize the $d_i$. So we would want $d_1 = 3, d_2 = 3, d_3 = 4, d_4 = 3, \ldots$ which indeed forms Fareed AF's sequence.

Answer 2

I might be wrong, but I think this set is the one with the most cardinal, because I think it has the least difference between its elements.

And this set is $\{1,4,7,11,14,17,21,24,27,31,34,37....\}$

we can notice that the last digit of each term will be either $1$,$4$, or $7$.

Which means from each 10 digits we will choose 3 digits.

So from 2019 digits we will choose 606 digits.