Take any 37 integers from the set $\{1,2,3,...112\}$, then show that there will always exist two integers out of those 37 integers such that $(x-y)\in\{9,10,19\}$
Here is my approach: Let the set of 37 numbers chosen be S. If we include any natural number n in set S we cannot include $n\pm9, n\pm10, n\pm19$ in the set S, that is if all these values are still within the set $\{1,2,3,...,112\}$. I am unable to rigorously prove that we cannot chose 37 numbers with the previous condition.
Can anybody please provide a rigorous proof for this.Thanks in advance