Biggest subset of $\{1, 2 ... 1000\}$ such that difference between any pair of elements $\neq 4, 7$

Question

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V \implies x \pm 4,x \pm 7 \notin V.$

What I've done so far: first let's generalize the upper bound on $S$ and call $f(n)$ the maximal subset size for $S = \{1, 2, ... n\}$.

I've conjectured that the optimal "tiling" pattern for such a subset is:

$$\dots \\ (x+11)+0, (x+11)+1, (x+11)+3, (x+11)+6, (x+11)+9, \\ (x+22)+0, (x+22)+1, (x+22)+3, (x+22)+6, (x+22)+9, \\ \dots$$

i.e. taking 5 elements for every cycle of 11. This would imply $$\lim_{n \to \infty}f(n) = \frac{5n}{11},$$ and hence $f(1000)\approx 454$. However, I don't know how to prove that this way of tiling the elements is optimal, and I also doubt this approach will yield an optimal packing to begin with (what about the edges of the set, around $1$ and $n$?)

Here's some solutions I generated using a Python script for small values of $N$. I don't know if they're of interest. The entries for $17 \leq N \leq 19$ clearly showcase the pattern I described above.

  n   f(n)  subset                           subset (graphically)
===================================================================
  0 |   0 |                                |                   
  1 |   1 | 1                              | x                 
  2 |   2 | 1, 2                           | xx                
  3 |   3 | 1, 2, 3                        | xxx               
  4 |   4 | 1, 2, 3, 4                     | xxxx              
  5 |   4 | 1, 2, 3, 4                     | xxxx.             
  6 |   4 | 1, 2, 3, 4                     | xxxx..            
  7 |   4 | 1, 2, 3, 4                     | xxxx...           
  8 |   4 | 1, 2, 3, 4                     | xxxx....          
  9 |   5 | 1, 3, 4, 6, 9                  | x.xx.x..x         
 10 |   5 | 1, 2, 4, 10, 7                 | xx.x..x..x        
 11 |   5 | 1, 2, 4, 10, 7                 | xx.x..x..x.       
 12 |   6 | 1, 2, 4, 7, 10, 12             | xx.x..x..x.x      
 13 |   7 | 1, 2, 4, 7, 10, 12, 13         | xx.x..x..x.xx     
 14 |   7 | 1, 2, 3, 4, 12, 13, 14         | xxxx.......xxx    
 15 |   8 | 1, 2, 3, 4, 12, 13, 14, 15     | xxxx.......xxxx   
 16 |   8 | 1, 2, 3, 4, 12, 13, 14, 15     | xxxx.......xxxx.  
 17 |   9 | 1, 3, 4, 6, 9, 12, 14, 15, 17  | x.xx.x..x..x.xx.x 
 18 |   9 | 1, 2, 4, 7, 10, 12, 13, 15, 18 | xx.x..x..x.xx.x..x
 19 |   9 | 1, 2, 4, 7, 10, 12, 13, 15, 18 | xx.x..x..x.xx.x..x.

Maybe I shouldn't tackle this question as a "packing" problem at all, and there's some clever trick I'm missing -- like finding the size of the set without having to actually describe it?

Answer 1

First we show that $f$ is subadditive, i.e. $f(m+n) \leq f(m) + f(n)$ for all positive integers $m,n$.

Suppose $V$ is a subset of $\{1,2,\ldots,m+n\}$ with the required property. Let $V_1 = \{x \mid x \in V \mbox{ and } x \leq m\}$ and $V_2 = \{x - m \mid x \in V \mbox{ and } x \geq m+1\}$. Then $V_1 \subseteq \{1,2,\ldots,m\}$ and $V_2 \subseteq \{1,2,\ldots,n\}$ and both have the required property, so $|V_1| \leq f(m)$ and $|V_2| \leq f(n)$ and $|V| = |V_1|+|V_2| \leq f(m) + f(n)$. Therefore $f(m+n) \leq f(m) + f(n)$.

Let $n = 11q + r$ where $0 \leq r \leq 10$ and $S = \{1,2,\ldots,n\}$. It follows from the subadditivity of $f$ that $f(n) \leq f(11)q + f(r) = 5q + f(r)$. Let $$V = \{x \in S \mid x \equiv 1,2,4,7,10 \bmod 11\}.$$ It is easy to check that $V$ has the required property. Also $V$ has $5q + f(r)$ elements iff $r \in \{0,1,2,7,8,10\}$, so for these values of $r$ we have $f(11q+r) = 5q + f(r)$.

In particular, $1000 = 11\cdot90 + 10$ and $10$ is a value of $r$ for which the upper bound is achieved, so $f(1000) = 5\cdot90 + f(10) = 455$.

It probably isn't too hard to work our what goes on when $r \in \{3,4,5,6,9\}$, but note that $f(11+r) \neq 5 + f(r)$ for $r \in \{3,4,5\}$. In fact if $n \in \{14,15,16\}$ then $V$ has $f(n)$ elements, so $f(11q + r) = 5(q-1) + f(11+r) = 5q + f(r) - 1$ when $q \geq 1$ and $r \in \{3,4,5\}$.

Addendum

If we replace $V$ by either of the sets (the former of which is found by @r9m) $$\{x \in S \mid x \equiv 1,3,4,6,9 \bmod 11\}, \mbox{and}$$ $$\{x \in S \mid x \equiv 1,4,6,7,9 \bmod 11\}$$ then the only change to the proof is for which values of $r$ we find that $f(11q+r) = 5q + f(r)$. In particular, the former set shows that this is true for $r \in \{6,9\}$.

Putting everything together we have proved the following:

Theorem Suppose $q \geq 1$ and $0 \leq r \leq 10$. If $r \notin \{3,4,5\}$ then $f(11q + r) = 5q + f(r)$. If $r \in \{3,4,5\}$ then $f(11q + r) = 5q + f(r) - 1$.

Answer 2

Think of $1,2,\ldots,1000$ as the vertices of a graph, where two vertices $i,j$ are joined by an edge if $|i-j| = 4$ or $7$. Then what you want is a maximum independent set for this graph.

EDIT: In this case a "dynamic-programming" method may be useful: let $F(n,s)$ be the best you can do with $n$ integers, including subset $s$ of the first $7$. Write down a recursion by looking at the cases where integer $8$ is or is not in your subset ...

Answer 3

Not sure if this answers your question. It is too long for a comment, and I want to be sure I understand your conjecture correctly.

First we are showing that we can choose a subset $A'$ of maximum $5$ elements from the set $A = \{1,2,3,\cdots,11\}$ which satisfies the property:

$\forall\, x,y \in A' \implies |x-y| \neq 4,7$

We can pick at most one element from each of : $$\{1,5\},\{2,9\},\{3,7\},\{4,11\},\{6,10\},\{8\}$$

Suppose if we were to choose a subset of $6$ elements with the required property, then : $$8 \in A' \implies 1 \notin A' \implies 5 \in A' \implies 9 \notin A' \implies 2 \in A' \implies 6 \notin A' $$ $$\implies 10 \in A' \implies 3 \notin A' \implies 7 \in A'\implies 11 \notin A' \implies 4 \in A'$$

Which leads to a contradiction!

Next comes the fact that $A'$ can be periodically extended to a set $V$ of greater cardinality, that satisfies the required property:

$\forall\, x,y \in V \implies |x-y| \neq 4,7$

$$V = \{11k + a|\,a\in A' \textrm{ and } k\in \mathbb{N}\} \subset S = \{1,2,3,\cdots,1000\}$$

Now, if we start with $A' = \{1,3,4,6,9\}$, we get $|V| = 455$.

Conversely, we cannot have a subset of size greater than $455$, since there will be a subset of $11$ consecutive integers in $S$, such that it has $6$ elements with the required property (by Pigeon Hole Principle), but which is absurd by the initial claim.