Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

4 Answers 4

up vote 6 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|improve this answer
    
Nicolas: Elegant. +1 –  user9413 Jun 8 '12 at 7:28
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.