The following problem appears in many Combinatorics books: Prove that among 70 positive integers less than or equal to 200 there are two whose difference is 4,5, or 9. The solution is straightforward using Pigeonhole principle. I was wondering is 70 the optimal number? I have tried to prove that we can get by with 64.
Let $A$ be any subset of $\{ 1, 2, 3, \ldots, 200\}$ such that no two integers in $A$ differ by 4, 5 or 9. Let for any integer $k$, $A+k$ represent the set $\{a+k: a \in A\}$. Note that \begin{equation*} A \cap A+4 = A \cap A+5 = A \cap A+9 = \phi \\ A+4 \cap A+ 9 = A+5 \cap A+9 = \phi \end{equation*} Thus \begin{equation*} |A \cup A+4 \cup A+5 \cup A+9| = 4|A| - |A+4 \cap A+5)| \end{equation*} Note that $A$ can not contain more than 4 consecutive numbers. Also, if it contains $i, i+1, i+2, i+3$, then $i+4, i+5, i+6, i+7, i+8, i+9, i+10, i+11, i+12$ can not belong to $A$. Thus in any set of 13 consecutive numbers, it can not contain more than 4 consecutive numbers. Note that $A+4 \cap A+5$ is maximum when $A$ contains as many consecutive numbers as possible. Thus when the maximum of $|A+4 \cap A+5|$ happens, we have $|A+4 \cap A+5|$ is at most $3 \times \lfloor \frac{200}{13}\rfloor + 4 = 49$. Hence \begin{equation*} 4|A| - 49 \leq |A| - |A+4 \cap A+5| \\ = |A \cup A+4 \cup A+5 \cup A+9| \\ \leq 209 \end{equation*} and $|A| \leq 64$.
A set with 64 elements satisfying the property is $$\{13k + 1, 13k+2, 13k+3, 13k+4: k = 0, 1, 2, \ldots, 15 \}$$ My question: Is the above proof correct?
Your proof looks O.K. to me. Anyway, your result is correct. Some comments:
Your introduction is slightly misleading. If you have quoted the problem correctly from the (unnamed) combinatorics books, then you have improved the number $70$ to $65,$ not $64.$ You have proved that, among $65$ positive integers less than or equal to $200,$ there are two whose difference is $4,$ $5,$ or $9.$
Perhaps a simpler approach is to prove that if $A$ is a set of integers, no two of which differ by $4,$ $5,$ or $9,$ then any set of $13$ consecutive integers contains at most $4$ elements of $A$ (regardless of whether those elements of $A$ are consecutive or not). To see this, suppose that the set $[13]=\{1,2,3,\dots,13\}$ contains $5$ elements of $A.$ Since each of the five sets $\{1,6,10\},\{2,7,11\},\{3,8,12\},\{4,9,13\},\{5\}$ contains at most one element of $A,$ we must have $5\in A.$ A similar argument shows that we must also have $9\in A,$ but this is absurd.
You have improved the $70$ to $65,$ but (apparently) you have not considered improving the $200?$ It seems that, among $65$ positive integers less than or equal to $208$ (or more generally $4n+1$ positive integers less than or equal to $13n$), there are two whose difference is $4,$ $5,$ or $9.$