70 distinct positive integers that are ≤ 200, there must be two whose difference is one of 4, 5, or 9

Question

Prove that among $70$ distinct positive integers that are $≤ 200$, there must be two whose difference is one of $4, 5,$ or $9$.

So from this there are $582$ possible pairs whose difference is $4,5,$ or $9$.

(i.e. $\{5,1\},\{6,2\},...,\{200,196\};\{6,1\},\{7,2\},...,\{200,195\};\{10,1\},\{11,2\},...{200,191}$).

Thus, since there are more possible pairs with qualifying differences than there are numbers to choose...

Suggestions?

Answer 1

First prove that if 5 numbers are choosen from a range of 13 consecutive integers then at least two have a difference of 4, 5 or 9. Once this is done there are at most 16 such ranges from 1 to 200 so at most 64 numbers can be placed before a pair of them have distance of 4, 5 or 9.

Now consider the pairs of triples:

A: (1,5,10) and (1,6,10)

B: (2,6,11) and (2,7,11)

C: (3,7,12) and (3,8,12)

D: (4,8,13) and (4,9,13)

Assume 5 numbers are placed in the interval 1 to 13, then either they are 5,6,7,8 and 9 or one of the numbers 5 to 9, say m, is not used.

I the first case 9-5=4. Otherwise select one triplet from each pair A .. D of triplets not containing m. Now each of the five placed numbers is in one of the four selected triplets so there is a pair with distance 4, 5 or 9.

Answer 2

We will show that if $A$ is any subset of $\{ 1, 2, 3, \ldots, 200\}$ such that no two integers in $A$ differ by 4, 5 or 9, then $|A| \leq 64$.

Let for any integer $k$, $A+k$ represent the set $\{a+k: a \in A\}$. Note that $A \cap A+4 = A \cap A = A \cap A+9 = A+4 \cap A+ 9 = A+5 \cap A+9 = \phi$. Thus \begin{align*} |A \cup A+4 \cup A+5 \cup A+9| &= 4|A| - |A+4 \cap A+5| \end{align*} 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 it contains as many consecutive numbers as possible. Thus 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 $$4|A| - 49 \leq 4|A| - |A+4 \cap A+5| = |A \cup A+4 \cup A+5 \cup A+9| \leq 209$$ and $|A| \leq 64$.

A set with 64 elements is $$\{13k + 1, 13k+2, 13k+3, 13k+4: k = 0, 1, 2, \ldots, 15 \}$$

Answer 3

A simpler solution for the problem as stated:

Let the numbers be

$$a_1, a_2,\ldots, a_{70}$$ and consider $$a_1, a_2,\ldots, a_{70}, a_1+4, a_2+4, \ldots, a_{70}+4, a_1+9, a_2+9, \ldots, a_{70}+9$$ There are 210 numbers and all are $\leq 209$. Thus some two must be equal. If $a_i = a_j+4$ or $a_i = a_j+9$, we are done. If $a_i+4 = a_j+9$, then $a_i = a_j+5$ and again we are done.