Existence of two natural number satisfying a given condition in a given set

Question

Suppose $A=\{1,2,\dots,112\}$, $B \subset A$ and the number of elements in $B$ is greater or equal to 37. Then, is it true that there always exist two elements $x,y \in B$ such that $x-y\in \{9,10,19\}$? Thanks in advance.

Answer 1

Let's prove the following ...

Claim: Let $S$ be a subset of $X=\{1,2,\dots , 28\}$ for which $a-b\not\in\{9,10,19\}$ for all $a,b\in S$. Then $|S|\le 9$.

By way of contradiction, assume that $|S|\ge 10$. Now arrange the elements of $X$ as follows.

\begin{array}{rrrrrrrrrr} 1&2&3&4&5&6&7&8&9&\\ 10&11&12&13&14&15&16&17&18&19\\ 20&21&22&23&24&25&26&27&28& \end{array}

Note that $S$ can contain at most one element from each column. However, as $|S|\ge 10$, $S$ must contain at least one element from every column. In particular, $19\in S$ is forced.

Now consider the following arrangement of the elements of $X$.

\begin{array}{rrrrrrrrrr} 1&2&3&4&5&6&7&8&9&10\\ 11&12&13&14&15&16&17&18&19\\ 20&21&22&23&24&25&26&27&28& \end{array}

By using the exact same reasoning as above, we see that $10\in S$ is forced. But this is a contradiction because $19-10=9$. Thus $|S|\le 9$ as claimed.

We may repeat this argument on the three remaining subintervals $\{29,\dots,56\}$, $\{57,\dots,84\}$, and $\{85,\dots,112\}$. This shows there are at most $9+9+9+9=36$ elements of $\{1,2,\dots,112\}$ with the desired avoidance property. Hence $|A|\ge 37$ will force the difference of some pair of elements of $A$ to be $9$, $10$ or $19$.