Find the maximal number of points, such that there exist a configuration of $2023$ lines on the plane, with each lines pass at least $2$ points.
Problem
Source: Thailand TSTST 2024 P11
Tags: combinatorics, induction
19.07.2024 16:25
First of all, the answer is $2023$, with the construction of $2022$ points lies on the same line $\ell$ and the last point doesn’t lies in $\ell$ \Next is the Bound, which we will change $2023$ to $n$ in order to generalize it. So, the remaining is to show that if there are $n$ lines on the plane, will be at most $n$ points satisfing the condition. $\bullet$Base Case ($n=3$): With 3 lines on a plane, the maximum number of intersection points is $3$. This is because any triplet of lines can form a triangle, and every triangle has exactly $3$ vertices (intersection points). $\bullet$ Inductive Step: Assume for any $k \leq n $, if there are $ k $ lines on a plane, the maximum number of intersection points is $ k $. We aim to prove that for $ k = n + 1 $, there can be at most $ n + 1 $ intersection points. $\bullet$ Contradiction (using Sylvester-Gallai theorem): Suppose there are $ n + 1 $ lines on a plane and more than $ n + 1 $ intersection points. According to the Sylvester-Gallai theorem, every set of points contains a line passing through exactly two points. If there are more than $ n + 1 $ points and $ n + 1 $ lines, at least one line must pass through exactly two points. This contradicts the assumption that there are more than $ n + 1 $ intersection points, since if we remove one of those two points, the line connecting them will disappear, leaving us with at most $ n$ lines and more than $n$ points, which contradicts the hypothesis. Conclusion: Therefore, if there are $ n $ lines on a plane, the maximum number of intersection points that can be formed is $ n $.