Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume you choose $1000$ different numbers from the group $\{1, 2, \dots,1997\}$.

Prove that within the $1000$ chosen numbers, there is a couple which sum is $1998$.

I defined:

  • pigeonholes: possible sums.
  • pigeons: the $1000$ different numbers.

Is this definition good or there is something better?

share|cite|improve this question
up vote 7 down vote accepted

Look at the pairs $(1,1997)$, $(2, 1996)$, and so on up to $(998,1000)$, together with the singleton $999$. These are the pigeonholes. Every number belongs to exactly one pigeonhole. If we choose $1000$ numbers, then since there are only $998$ pairs and $1$ singleton, at least $2$ of our numbers end up being in the same pigeonhole, that is, adding up to $1998$.

share|cite|improve this answer
Nicolas: Elegant. +1 – user9413 Jun 8 '12 at 7:28

I would consider the sets $A_1 = \{1,1997\}, A_2 =\{2,1996\} \ldots A_{998} = \{998, 1000\}, A_{999}=\{999\}$. Note that they contain all the numbers ${1,\ldots , 1997}$.

Now, we want to choose $1000$ numbers: it means that you take at least two elements from the same set and hence their sum is indeed $1998$.

share|cite|improve this answer

Consider the sets $S_k = \{k,1998-k\}$, where $k \in \{1,2,\ldots,998,999\}$. Note that $S_{999} = \{999\}$.

Now you have $999$ pigeon-holes.

You now need to choose $1000$ numbers from $S = \displaystyle \bigcup_{k=1}^{999} S_k$ i.e. from the $999$ sets/pigeon-holes.

Hence, there must be two numbers from one set. Call that set $S_l$.

The two numbers in $S_l$ are $l$ and $1998-l$. They add up to give $1998$.

share|cite|improve this answer

There’s something better. The $1000$ numbers are your pigeons, but your pigeonholes won’t work. Break up the set $\{1,\dots,1997\}$ into pairs of numbers that add up to $1998$: $\{1,1997\},\{2,1996\},\dots$. These pairs are your pigeonholes; how many are there?

You need to be a little careful here, since $1997$ is odd: after you form the pairs, you’ll have one number left over. It’s a pigeonhole all by itself.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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