Pigeonhole Principle Problem combo inequality

Question

Prove that for any subset of $\{1,2,3,...,300\}$ with $102$ elements, there exists elements $M$ and $x$ in that subset such that $100<M-x<200$.

I think this is a pigeonhole problem, I wanna construct $101$ pigeonholes but in vain, may anyone give a help here.

Answer 1

Hint: Put all 300 points on a circle. We want to show that some $a$ in the chosen set has a point which is in the 99 points opposite it on the circle.

---

Solution: If not, then pick any $a$ in the set; the remaining 101 points lie in the 200 spots surrounding $a$. Pair these up so that the furthest anticlockwise is paired with the nearest clockwise, with the distance within a pair exactly 101 or 199. There are one hundred pairs and 101 points to place, so some pair contains two points, a contradiction.

Not sure if there's a neater way.

Answer 2

Let $N=100$, and let $A$ be a subset of $\lbrace 1,2,3,4, \ldots, 3N\rbrace$ containing at least $N+2$ distinct elements. We have to find $x,y\in A$ with $N \lt y-x \lt 2N$.

Let $B=A \cap \lbrace 1,2,3,4, \ldots, N+1\rbrace$ ; denote by $t$ the number of elements in $B$, and by $b_1 \lt b_2 \lt \ldots \lt b_t$ the elements in $B$. Suppose first that $t\neq 0$.

If one of the $N-1$ elements $b_1+(N+1),b_1+(N+2), \ldots , b_1+(2N-1)$ is also in $A$, taking $x=b_1$ we are done.

If one of the $t-1$ elements $b_2+(2N-1), \ldots, b_t+(2N-1)$ is also in $A$, then we may take $y$ to be that element and we are done.

Otherwise, we have just excluded $N-1+t-1$ elements from $A$, so

$$|A\cap \lbrace N+2,N+3 \ldots,3N \rbrace| \leq |\lbrace N+2,N+3 \ldots,3N \rbrace|-(N+t-2)=(2N-1)-(N+t-2)=N-t+1.$$

The total number of elements in $A$ is then at most $t+N-t+1=N+1$, contradiction.

So we must have $A \cap \lbrace 1,2,3,4, \ldots, N+1\rbrace=\emptyset$, and by symmetry $A \cap \lbrace 2N-1,2N, \ldots, 3N\rbrace=\emptyset$. But then $A \subseteq \lbrace N+2,N+3, \ldots, 2N-2\rbrace$ and $A$ has at most $N-3$ elements, contradiction.

Answer 3

Suppose that there is a subset $S$ with 102 elements that does not satisfy the desired property. Then for every pair of elements $(M,x)$ in the subset, either $M - x \le 100$, or $M - x \ge 200$.

Since $|S| = 102$, it must be that $\max S - \min S \ge 101$, so $\max S - \min S \ge 200$. Hence $\min S \le \max S - 200 \le 300-200 = 100$.

Let $S_1 = \{x \mid \max S - x \ge 200\}$, which contains $\min S$ and is therefore non-empty. Let $S_2 = \{x \mid \max S - x \le 100\}$, which contains $\max S$ so is also non-empty. Now let $M = \min S_2$ and $x = \max S_1$. If $M - x \ge 200$ then $\max S - x = (\max S - M) + (M - x) \ge \max S + 100$, a contradiction, so $M - x \le 100$. Then $\max S - x = (\max S - M) + (M - x) \le 200$. Hence $\max S = x + 200$, so $M = x + 100$ and $\max S = M + 100$. Then $S_2 = \{M,\max S\}$ and $S = \{1,2,\dots,100,200,300\}$. However, this set does not satisfy the requirement since $200 - 2 = 198$.

This contradiction shows that every subset with 102 elements must satisfy the property.