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

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

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


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


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.