Pigeonhole Principle and sets homework

Question

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$.

Answer 1

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{[1]}}$). 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:

[1] 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.