On the plane, there are 998 red points, no three of which are collinear. We mark blue points in such a way that there is a blue point inside every triangle whose vertices are red points. What is the positive integer $k$ for which it is always possible to achieve this using $k$ blue points, but there is an arrangement of the red points for which $k-1$ points are not sufficient?
Solution. We will show that the sought number is 1991; in general, for $n$ red points, where $n \geq 3, 2n-5$ blue points are needed, no more.

![](https://cdn.mathpix.com/cropped/2024_05_02_c396c616c702ea5e5669g-1.jpg?height=488&width=634&top_left_y=249&top_left_x=732)

First, we give a system of points $P_{i}, i=1,2, \ldots, n$ for which at least $2n-5$ blue points are needed. For example, draw a circular arc from $P_{3}$ to an interior point of the side $P_{1} P_{2}$ of the triangle $P_{1} P_{2} P_{3}$, and mark the remaining $n-3$ points in its interior (Fig. 3). Then none of the triangles $P_{1} P_{i} P_{i+1}, P_{2} P_{i} P_{i+1} (3 \leq i \leq n-1)$ and $P_{1} P_{2} P_{n}$ have a common interior point, so there must be a blue point in the interior of each. Thus, at least

$$
2(n-3)+1=2n-5
$$

blue points are needed.

Now let $P_{1}, P_{2}, \ldots, P_{n}$ be an arbitrary system of red points. We provide a procedure for placing the blue points. Choose a line $e$ that is not parallel to any line $P_{i} P_{j}$, and a sufficiently small distance $d$, for example, smaller than the heights of all triangles with red vertices. This is possible because there are only finitely many point pairs and finitely many triangles.

Now draw a line $e_{i}$ parallel to $e$ through each point $P_{i}$. Then there will be an $e_{u}$ whose one side has no red points, and an $e_{v}$ whose side not containing $e_{u}$ has no red points.

There are no red points on these lines other than $P_{u}$ and $P_{v}$, because there are no three red points on a line, and according to the choice of $e$, neither of these lines can have two. Every other line $e_{i}$ intersects the segment $P_{u} P_{v}$, which lies inside the convex hull of the point system.

Place a blue point on each ray starting from $P_{i}$ at a distance $d$ from $P_{i}$, which has a common point with the interior of the convex hull. With this, we have met the requirements of the problem. The lines through the vertices of a red triangle, in fact, differ from the side lines. Thus, one of the lines has a common point with the interior of the triangle. The blue point marked on this is inside the triangle due to the choice of $d$.

Let's count the blue points. We placed two blue points near each red point inside the convex hull, and one blue point near each red point on the boundary of the convex hull, except for $P_{u}$ and $P_{v}$, to which we did not place blue points. Let $b$ be the number of vertices of the convex hull. There are $n-b$ red points inside the convex hull. The number of blue points is therefore

$$
2(n-b)+b-2=2n-b-2 \leq 2n-5
$$

With this, we have also proven the second part of the statement to be proven.

Remarks: 1. Instead of parallel lines, we can choose a point $O$ outside the convex hull such that it is not on any line $P_{i} P_{j}$, and place the blue points on the lines $e_{i}=O P_{i}$ according to the above prescription.

2. It is easy to see that in the general case, $2n-b-2$ blue points are needed. This follows if we show that no matter how we decompose the convex hull of the points into triangles, none of which have a common interior point, the number of triangles is always $2n-b-2$. This is also true if more than two points can lie on a line, just not all.

A decomposition with the desired properties exists. We can obtain one, for example, by decomposing the convex hull of the point system into triangles with diagonals from a vertex, then taking a point that is not a vertex of any drawn triangle and connecting it to the vertices of the triangle or triangles containing it. In a finite number of points, we can reach a decomposition with the desired properties in a finite number of steps.

Denoting the number of triangles in a decomposition with the desired properties by $h$, the sum of the angles in these triangles is $h \cdot 180^{\circ}$. The vertices of these angles are the points of our point system. Around each point inside the convex hull, a total of $360^{\circ}$ is formed (independently of the decomposition). The sum of the angles formed around the points on the boundary of the convex hull, however, is the sum of the angles of a $b$-gon, which is $(b-2) \cdot 180^{\circ}$. Thus,

$$
h \cdot 180^{\circ}=(n-b) \cdot 360^{\circ}+(b-2) \cdot 180^{\circ}, \quad \text { so } \quad h=2n-b-2,
$$

as stated.[^0]

[^0]:    ${ }^{1}$ If a polygon has additional points on its sides, and we consider each of these as vertices with an internal angle of $180^{\circ}$, the formula for the sum of the angles clearly remains valid.