3. Determine the smallest natural number $k$, for which the following holds: If we select any $k$ different numbers from the set $\{1,2,3, \ldots, 2000\}$, then among the selected numbers there exist two whose sum or difference is 667.

School - written part of the first round, category A takes place

## on Tuesday, December 7, 1999

so that it starts in the morning and the contestants have 4 hours of pure time to solve the problems. For each problem, a contestant can earn 6 points, and a successful solver is a student who scores 10 points or more. These details will be communicated to the students before the start of the competition.
3. We will show that the desired $k$ is the number 1001. Let's divide all numbers from the set $\{1,2,3, \ldots, 2000\}$ into 1000 pairs

$$
\begin{gathered}
\{1,666\},\{2,665\},\{3,664\}, \ldots,\{333,334\}, \\
\{667,1334\},\{668,1335\},\{669,1336\}, \ldots,\{1333,2000\} .
\end{gathered}
$$

(The number 667 from the problem statement is equal to the sum of the numbers in each pair in the first row and the difference of the numbers in each pair in the second row. Note that each of the numbers $1,2,3, \ldots, 2000$ is represented in exactly one pair.)

The number 1001 has the required property because if we select any 1001 numbers from the set $\{1,2,3, \ldots, 2000\}$, there will be both numbers of at least one of the given pairs among them (we have selected 1001 numbers, but there are only 1000 pairs). The sum or difference of the numbers in the found pair is 667.

Now we will show that no number $k \leqq 1000$ has the required property. It is sufficient to show this for $k=1000$: if we select 1000 even numbers $2,4,6, \ldots, 2000$, the sum and difference of any two selected numbers are even, so they cannot equal the odd number 667.

Full solution is worth 6 points. Award 4 points for proving that the number 1001 has the required property and 2 points for proving that the number 1000 does not.