Problem concerning the use of Pigeonhole (Box) principle

Question

Question:

Take any $37$ integers from the set {${1,2,…,112}$}. Show that there will always exist two integers $x,y$ out of those $37$ integers such that $ \mid x-y \mid \in \{9,10,19\}$.

Approach:

What have I done so far:

Let $S=$ {${1,2,…,112}$}

We partition the set into subsets $S_i$ of the form $\{x, x+9, x+19\}$. Then the difference of any two elements is in $\{9, 10, 19 \}$, which is easy to see.

The following partitions are made (for $x=1, 2, \cdots , 9$): $$\{1, 10, 20 \}, \{2, 11, 21 \}, \cdots, \{9, 18, 28\}$$ Then next we choose $x=29$ to maintain the disjoint sets essential for our proof. This gives the disjoint sets $$ \{29, 38, 48\}, \cdots, \{37, 46, 56 \} $$ and similarly $$\{85, 94, 104 \}, \cdots, \{93, 102, 112 \}$$

However as the quick reader may see that the numbers $\{19, 47, 75, 103\}$ do not occur in any set. However, I decide to do a case by case analysis of the situations. Name this set as $X$.

Suppose, initially, that out of the $37$ integers in our selection, none belong to $X$. Then it follows from Dirichlet's box principle that at least two elements are from the same set (i.e. from one of the subsets that we partitioned $S$ into) then the claim is valid.

Now suppose that one element from $X$ is in our selection, say $19$ then if at least one of $9, 28, 29, 38$ is in our selection, then the claim is valid.

Suppose none of these are present, and we are deficit in four integers. We can now select any four integers from the remaining numbers and the box principle guarantees that at least two are from the same set.

For, even if all $3$ other elements of $X$ are now present, there is one empty slot which can be filled using the other subsets from where we already have at least one element in our choice of $37$ numbers.

I hope this is comprehensible because my combinatorics proof writing abilities are horrible. I am preparing for Olympiads and also for being a good Mathematician in general. Thank you for the help :)

Edit:

It seems I didn't enter my main question, apologies. Is my solution correct?

Answer 1

Nice job, I think your reasoning is all there but it will help to break down your argument a little bit, to make it easier to read.

First you partitioned the interval $\{1,\cdots 112\}$ into $37$ sets, all of the form $S_x = \{x, x+9, x+19\}$ except for the exceptional set $X = \{19, 47, 75, 103\}$. Then we examine how $X$ interacts with the $S_x$. For any $z \in \{1,\cdots 112\}$, define $$B_z = \big\{y \in \{1,\cdots 112\} \text{ such that } |y-z| \in \{9,10,19\} \big\}$$

We make the important observation that for each $y \in X$, $B_y \supset S_{y-10}$. That is to say, for each element we place in $X$, we invalidate an additional $S_x$.

Now we have to place $37$ elements among the $37$ sets.

Suppose we place $0 \leq n \leq 4$ elements in $X$. This leaves $37 - n$ elements to place among the $36$ $S_x$. From the above observation, $n$ choices of the $S_x$ will immediately result in elements a 'bad' distance apart. So only $36 - n$ choices of the $S_x$ are viable. We are thus placing $37 - n$ elements in $36 - n$ of the $S_x$, and by pidgeonhole, one of the $S_x$ must contain two elements.

Answer 2

Just to show another possible way to tackle the problem.

Taking $S=\{1,\,2,\, \cdots,\,112\}$ or $S=\{0,\,1,\, \cdots,\,111\}$ or any set of $112$ consecutive integers clearly does not change the problem. Let's fix $S=\{0,\,1,\, \cdots,\,111\}$.

Then taking the set $T$ of $37$ integers, it is also clear that if we shift it as to have the minimum at $0$ does not change the problem.

Therefore we can start $T$ as $\{0,\, 1,\, 2,\, \cdots,\, 8\}$ (tot. of $9$ integers)
after which we shall jump the set $\{9,\, \cdots,\,18\} $ and $\{19,\, \cdots,\,27\} $ , i.e. $19$ integers.

The most compact way that we can proceed with is to repeat the above starting with $28$.

To reach to $|T|=37$ we need to fix $4$ banned sets, i.e. $76$ integers.
But $112-76=36 < 37$, so we cannot avoid that at least one integer be in banned set.