Let set A is subset of set $\{{1,2,3,...,100}\}$ which has $55$ different elements.

Question

Let set $A \subset\{{1,2,3,...,100}\}$ with $55$ distinct elements.

Prove that there exist two elements in $A$ which have a difference of 10.

I understand that the common thing is that we take more than a half set $\{{1,2,...,100}\}$ elements, but how to prove it in right way?

Answer 1

Pair up the elements in pairs which differ by $10$ ($1$ gets paired with $11$, $2$ with $12$, etc., $21$ with $31$, etc.). There are $50$ pairs. Since you're choosing more than $50$ elements, by the Pigeonhole Principle, at least one pair must have both elements chosen.

Answer 2

We will tackle the alternate problem of finding the largest $m$ so that there exists a subset $A_m$ of $\{1,2,...,100\}$ so that there are no two elements that have a difference of $10$.

Note that for any subset $B$ of $\{1,2,...,100\}$ can be split into a disjoint union $B_0\cup B_1\cup B_2\cup B_3\cup B_4\cup B_5\cup B_6\cup B_7\cup B_8\cup B_9$ such that $y \in B_i$ iff $y \equiv i $ $mod(10)$. If any of the sets $B_i$ contain $6$ elements there exist two elements in $B_i$ with difference $10$; thus we have the bound $m \leq 50$

Now if we fill $B_i$ to contain the elements $i$ $mod(20)$ we indeed obtain the bound $m \geq 50$; thus by above $m = 50$.

So we have showed that if $A$ even has as little as $51$ elements there are at least two elements with difference of $10$.

Answer 3

Here is a proof by contradiction.

Suppose you are able to identify 55 elements and there are no two elements which difference equals to 10. So pick the first element $x_1$, then it is forbidden to pick the elements $x_1 +10$ and $x_1 -10$ (if within the range [1, 100]). Sorting the elements you pick in ascending order, this reduces to the fact that for each element you pick, you get one element $x_1 +10$ (if within the range [1, 100]) that you are forbidden to pick. Now for the last 10 elements you could pick within the range [91, 100] this results in no restrictions.

So a candidate for the best case is the following: consider first the 90 elements in the range [1, 90]: if possible, you pick 45 elements in the range [1, 80] which results in 45 forbidden elements in the range [11, 90]. Then you can pick the ten elements in [91, 100] which result in no restrictions. So this would result in picking 55 elements. All other cases would result in one more restriction, and you could only pick less than 55 elements, so there you have a contradiction.

So the only way to be able to pick 55 elements is that "best case" construction, but is it available? Well, no: the above construction assumed that you pick 45 elements in the range [1, 80] which results in 45 forbidden elements in the range [11, 90]. However, that is not possible. Since picking 45 elements in the range [1, 80] means that you should only create 35 forbidden elements in the range [1, 80], which in turn means that 10 of the forbidden elements must be in [81, 90]. So you must actually pick the elements [71, 80] to guarantee that. Continuing with that argument recursively, you actually pick the elements in the ranges [11, 20] [31, 40] [51, 60] [71, 80] [91, 100] which are just 50. So the "best case" construction is not available. This completes the contradiction proof.