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.

  • $\begingroup$ Hint: The fact that $9+10=19$ is very relevant to this problem. $\endgroup$ – Doc Nov 25 '13 at 4:21
  • $\begingroup$ Hint to prove or disprove? $\endgroup$ – D. N. Nov 25 '13 at 4:24
  • $\begingroup$ 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. $\endgroup$ – Doc Nov 25 '13 at 4:43
  • $\begingroup$ 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.) $\endgroup$ – Doc Nov 25 '13 at 4:54
  • $\begingroup$ 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$. $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.