Given a positive integer $k$, find the largest positive integer $m$ such that the following holds: if among $3k$ different points in the plane, at most $m$ lie on a single line, then the points can be divided into $k$ groups of three in such a way that the points in each group are the vertices of a triangle.
Solution. We will show that $m=2k$.

First, we observe that if there is a line that contains at least $(2k+1)$ of the $3k$ points, then the points cannot be divided into $k$ groups of three such that the points in each group form the vertices of a triangle. This immediately follows from the fact that any three points of a triangle can have at most two points on any line, so $k$ different triangles can have at most $2k$ points on any line.

If there is no line that contains more than $2k$ of the $3k$ points, then we will prove by complete induction on $k$ that the points can be divided into $k$ groups of three such that the points in each group form the vertices of a triangle. If $k=1$, then by our condition, the three points are not collinear, so they form the vertices of a triangle, and the statement is true. We also prove the case $k=2$ separately because in the inductive step, we will use the fact that the number of points is at least 6. If no three of the points are collinear, then we can divide them into two groups in any way, and the points in each group will form the vertices of a triangle. If exactly four of the points, say $A, B, C$, and $D$, lie on a line $e$, and the remaining two, $E$ and $F$, do not lie on $e$, then, for example, $\{A, B, E\}, \{C, D, F\}$ is a valid arrangement (Figure 1). Finally, if no four of the points are collinear, but, for example, $A, B$, and $C$ lie on a line $e$, then we choose two points from the remaining three, say $D$ and $E$. We can assume that the intersection point of lines $DE$ and $e$ is not $A$. If the sixth point is $F$, then, for example, $\{A, D, E\}, \{B, C, F\}$ is a valid arrangement (Figure 2).

![](https://cdn.mathpix.com/cropped/2024_05_02_f5f6b500f3e58067f824g-1.jpg?height=220&width=420&top_left_y=828&top_left_x=836)

Figure 1

![](https://cdn.mathpix.com/cropped/2024_05_02_f5f6b500f3e58067f824g-1.jpg?height=319&width=466&top_left_y=1155&top_left_x=819)

Figure 2

Suppose the statement is true for $k=n>1$. Let there be given $3(n+1)$ distinct points such that at most $2(n+1)$ of them lie on a line. Consider the lines that contain at least two of the points. Let the number of these lines be $N$. (The number of such lines is finite, since the inequality $N \leq \binom{3n+3}{2}$ clearly holds.) Let these lines be $\ell_{1}, \ell_{2}, \ldots, \ell_{N}$, and choose the numbering such that if $|\ell_{i}|$ is the number of given points on line $\ell_{i}$, then for all $i=1,2, \ldots, N-1$, the inequality $|\ell_{i}| \geq |\ell_{i+1}|$ holds (the numbering is not unique because there can be lines that contain the same number of points).

First, we show that $|\ell_{3}| < 2n+2$. If $|\ell_{3}| \geq 2n+2$, then the points on $\ell_{1}$ and $\ell_{2}$ would be at least $2(2n+2) = 4n+4$. Since $n>1$, we have $6n > 3n+3$, and this contradiction implies that $|\ell_{3}| < 2n+2$. Next, we show that $|\ell_{2}| < 2n+2$. If $|\ell_{2}| \geq 2n+2$, then the points on $\ell_{1}$ and $\ell_{2}$ would be at least $2(2n+2) = 4n+4$. Since $n>1$, we have $6n > 3n+3$, and this contradiction implies that $|\ell_{2}| < 2n+2$. Finally, we show that if $i \geq 2$, then $|\ell_{i}| \leq 2n$. Choose two points arbitrarily from the points on $\ell_{1}$ and add a third point from the points on $\ell_{2}$ that is not on $\ell_{1}$. These three points clearly form a triangle. For the remaining $(3n+3)-3=3n$ points, the inductive hypothesis holds because no $2n$ of them lie on a line. Since only the lines $\ell_{i}$ contain at least two of the points, the number of remaining points on $\ell_{1}$ is at most $(2n+2)-2=2n$, the number of remaining points on $\ell_{2}$ is at most $(2n+1)-1=2n$, and for the other lines, $|\ell_{i}| \leq 2n$ holds. Therefore, these points can be divided into $n$ groups of three such that the points in each group form the vertices of a triangle. Hence, the $3n+3$ points can also be divided into groups that satisfy the conditions, and this completes the proof of our statement.