# Pigeonhole Principle and sets homework

Can someone help me with this question? I'm having trouble solving this problem. I don't know where start.

Let $$S$$ be a set of integers with the following properties:

1. Every element of $$S$$ is between $$1$$ and $$2014$$ (inclusive).

2. $$S$$ has at least $$1008$$ elements.

Use the Pigeonhole Principle to show that $$S$$ contains two numbers whose sum is exactly $$2015$$.

• Consider the $1007$ pigenholes $\{1,2014\}$, $\{2,2013\}$, $\ldots$, $\{1007,1008\}$. – Winther Nov 25 '15 at 3:24
• We need the elements of $S$ to be distinct. – Mike Pierce Nov 25 '15 at 3:27
• @MikePierce They should be, as $S$ is a set. – Clement C. Nov 25 '15 at 3:27

## 1 Answer

Set $S$ has $1008$ integer elements in the range $[1,2014]$. Take $S' = \{2015-s \mid s \in S\}$. This set $S'$ also has $1008$ elements. If we we look at $S \cap S'$, this intersection must be nonempty (why? $^{\mathrm{}}$). Take some $x \in (S \cap S')$. For this $x$ there is the element $(2015-x) \in S$. These values $x$ and $(2015-x)$ are two elements of $S$ that sum to $2015$.

Footnotes:

 This is where you apply the pigeonhole principal. The set $S$ and $S'$ both have $1008$ elements. Because the range of $S$ is $[1,2014]$, the range of $S'$ is also $[1,2014]$. If we were to suppose that $S \cap S'$ is empty (so they have no common elements), then $S \cup S'$ would have to have $1008+1008 = 2016$ elements. But this is too many elements since there are only $2014$ integers in the range $[1,2014]$. So $S \cap S'$ must be nonempty.