5
$\begingroup$

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?

4 Answers 4

7

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

  • 0
    Nicolas: Elegant. +12012-06-08
2

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

2

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

1

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.