
Problem 1. In an orthogonal coordinate system $x O y$ a set consisiting of 2000 points $M_{i}\left(x_{i}, y_{i}\right)$, is called "good" if $0 \leq x_{i} \leq 83,0 \leq$ $y_{i} \leq 1 \quad i=1,2, \ldots, 2000$ and $x_{i} \neq x_{j}$ for $i \neq j$. Find all natural numbers $n$ with the following properties: : a) For any "good" set some $n$ of its points lie in a square of side length 1 .

b) There exists a "good" set such that no $n+1$ of its points lie in a square of side length 1 .

(A point on a side of a square lies in the square).


Solution: We shall prove that $n=25$ is the only solution of the problem. We show first that for a "good" set some 25 points lie in a square of side length 1 . All points lie in the rectangle $1 \leq$ $x \leq 83,0 \leq y \leq 1$. Divide this rectangle to 83 squares of side length 1. If some 25 points lie in one of these rectangles then we are done. Conversely, in every square there are at least 26 or at most 24 points. We prove now that there exists a square with at least 26 points and there exists a square with at most 24 points. Indeed, if a square with 26 points does not exist then the points are at most $83.24=19922000$. Further, move the square with more than 25 points towards the square with less that 25 points. Since the number of points in this square changes at most by one we get the assertion of the problem.

To prove b) let $x_{1}=0, x_{i}=x_{i-1}+\frac{83}{1999}$ and $y_{i}=0$ for $i=$ $0,2,4, \ldots, 2000$ while $y_{i}=1$ for $i=1,3, \ldots, 1999$. Let $X Y Z T$ be an unit square. WLOG we assume that it intersects the lines
$y=0$ and $y=1$ in the points $P, Q$ and $R, S$ respectively. Then

$P Q+Q R+R S+S P<P Y+Y Q+Q Z+Z R+R T+T S+S X+X P=4$

But $S P, Q R \geq 1$ and we get $P Q+R S<2$. This implies that in the square $X Y Z T$ there are no more than 25 points.

We found that $n=25$ is a solution of the problem. It is unique since $24<\frac{2000}{83}<25$.
