5. Find the smallest natural number $n$ such that for every set of $n$ points with integer coordinates, of which no three lie on the same line, there exists a triangle with vertices from this set for which the midpoints of its sides also have integer coordinates.

No use of a pocket calculator or any manuals is allowed.

## NATIONAL MATHEMATICS COMPETITION
5. Find the smallest natural number $n$ such that for any set of $n$ points with integer coordinates, of which no three lie on the same line, there exists a triangle with vertices from this set for which the midpoints of its sides also have integer coordinates.

## Solution.

If the points are $A\left(x_{1}, y_{1}\right)$ and $B\left(x_{2}, y_{2}\right)$, then their midpoint is given by

$$
P\left(\frac{x_{1}+x_{2}}{2}, \frac{y_{1}+y_{2}}{2}\right)
$$

Divide all points with integer coordinates into four sets:

$S_{1}$ - the set of points whose abscissa and ordinate give a remainder of 1 when divided by 2,

$S_{2}$ - the set of points whose abscissa and ordinate are divisible by 2,

$S_{3}$ - the set of points whose abscissa gives a remainder of 1 when divided by 2, and whose ordinate is divisible by 2,

$S_{4}$ - the set of points whose abscissa is divisible by 2, and whose ordinate gives a remainder of 1 when divided by 2.

Among 9 points, by the Dirichlet principle, there must be 3 points that belong to one of the four sets mentioned above. These three points are the vertices of a triangle (since no three points lie on the same line), and for these three points, it is true that the midpoint of each of the three segments they determine (which are the sides of the triangle) has integer coordinates, because the sum of the abscissas, as well as the sum of the ordinates, of any two such points is an even number, as per (1).

If we have a set of 8 points, with two from each of the sets $S_{1}, S_{2}, S_{3}$, and $S_{4}$, for example, the set consisting of the points $(0,0), (0,2), (1,0), (1,2), (2,1), (2,3), (3,1)$, and $(3,3)$, then among any 3 chosen points, there will be at least two points from different sets $S_{1}, S_{2}, S_{3}$, and $S_{4}$. Since the sum of the abscissas or the sum of the ordinates of two points from different sets is not even, according to (1), the abscissa or the ordinate of some midpoint is not an integer.

(The image shows the selected eight points, none of which are on the same line.)

![](https://cdn.mathpix.com/cropped/2024_05_30_ba00de53bdad84e80dffg-19.jpg?height=865&width=870&top_left_y=230&top_left_x=593)

Therefore, the smallest natural number $n$ with the desired property is $n=9$.

## NATIONAL MATHEMATICS COMPETITION