Problem concerning the use of Pigeonhole (Box) principle

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?

• What is your question? Feb 24 '18 at 17:09
• I understand the math question. Are you asking whether your solution is correct? Feb 24 '18 at 17:12
• @saulspatz yes sorry Feb 24 '18 at 17:13
• I have trouble understanding the two paragraphs starting with, "Suppose none of these are present ..." I'm not saying they're wrong, just difficult to follow. It might be better to say, "Suppose none of them are present. Then the remaining 36 choices come from as set of 107 elements ..." Feb 24 '18 at 17:19
• @saulspatz i want to say that if from our selection of the 37 integers in S, at least one of 9, 28, 29, 38 are present in addition with our choice of 19, then we have our claim. Then we suppose that none of these are present, so 19 cannot form the pair required. Feb 24 '18 at 17:21

2 Answers

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.

• Thank you so much. I am very new to Olympiad Combinatorics and in fact this is my first takedown on an AoPS combi problem. Your contribution fixes my proof altogether. Thank you so much. I still need a way to hone my proof writing skills. Thanks again :) Feb 24 '18 at 18:15
• Don't worry! The creative part of the problem was figuring out how to construct a partition and apply the pigeonhole principal, and you got that. The rest will follow naturally from practice, and especially practicing verbal math communication with other human beings. Feb 24 '18 at 18:37

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.