Pigeonhole Principle Problem combo inequality 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.
 A: 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.
A: 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.
A: 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.
