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.


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.


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.