Consider the set $A=\{1,2,3,...,2000\}$. We are asked to find a subset of maximum size so that the difference of any two members of this subset is not a prime number. I think one subset of maximum size can be $\{1,5,..., 1397\}$. i.e., numbers of the form $4k-3$ for natural $k$. It is easy to show that one can not add more elements to this set as its difference with some element would be $ 2,3$ or $5$. Hence the maximum size of such subsets is $500$. Now we have to prove that in any set of $501$ elements chosen from $A$, there are always two elements whose difference is a prime number. To do so, we apply the pigeonhole principle to the holes $\{1,2,3,4\}, \{5,6,7,8\}, \dots \{1997,1998,1999,2000\}$ and $501$ numbers as pigeons. Please help me if the proof is complete or not. If not, how to show that $500$ is the maximum size? What are the suitable holes?
Thank you.
Here is an argument for not more than $500$ elements of $S$.
We will use your pigeonholes of $\{1,2,3,4\}, \{5,6,7,8\},...\{1997,1998,1999,2000\}$. That is, the pigeonhole sets are of the form $\{4k+1,4k+2,4k+3,4k+4\}$ for $k=0,1,...,499$.
Let $S$ be the set with no prime differences that we are constructing.
Suppose there are two elements in $S$ from any of the pigeonhole sets, they must differ by $1$ (since the other options are to differ by $2$ or $3$, both prime). I claim that (1) there are then no numbers from the next (greater) pigeonhole set in $S$; and (2) there are no numbers from the previous pigeonhole set.
For (1) there are three cases:
Case 1: $4k+1$ and $4k+2$ are in $S$, but then each element of the next pigeonhole set ($\{4k+5, 4k+6, 4k+7, 4k+8\}$ cannot be in $S$. [We have $(4k+5)-(4k+2)$ is prime; $(4k+6)-(4k+1)$ is prime, $(4k+7)-(4k+2)$ is prime, and $(4k+8)-(4k+1)$ is prime.]
Cases 2 and 3: Where respectively $4k+2$ and $4k+3$ are in $S$ and $4k+3$ and $4k+4$ are in $S$ are similar.
For (2) (nothing in the previous pigeonhole set), the cases are similar.
We conclude that if there are two elements from one pigeonhole, then this is balanced out by no elements from the next or previous pigeonhole set. So again there are at most $2$ out of any $8$ consecutive numbers in $S$. So $S$ cannot contain more than $500$ elements.