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

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.

• Hint: The fact that $9+10=19$ is very relevant to this problem. – Doc Nov 25 '13 at 4:21
• Hint to prove or disprove? – D. N. Nov 25 '13 at 4:24
• Well, the way the problem was structured, I thought it would be relevant, but apparently you can prove the statement is true with any triple of forbidden differences in this case. – Doc Nov 25 '13 at 4:43
• Well, the way the problem is structured, I would tend to think it's true. But I need to check the details. (Until then, scratch my last comment.) – Doc Nov 25 '13 at 4:54
• Here's my reasoning as I go along. See if any of this helps. There are $111$ possible differences that can be formed by the difference of two numbers in $A$, and $37\choose 2$ ways of picking $x_i,x_j\in A$ with $x_i<x_j$. – Doc Nov 25 '13 at 5:02

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$.

• Thank you so much. It is a very nice one. – D. N. Nov 27 '13 at 4:58
• Any time. I will definitely be conscious of your posts in the future. It was a real pleasure to work with you. – Doc Nov 27 '13 at 5:02
• It is very kind of you. Again i should say thank you so much. – D. N. Nov 27 '13 at 5:07