Problem

Source: 2025 Korea Winter Program Practice Test P6

Tags: combinatorics



There are $n$ parallel lines on a plane, and there is a set $S$ of distinct points. Each point in $S$ lies on one of the $n$ lines and is colored either red or blue. Determine the minimum value of $n$ such that if $S$ satisfies the following condition, it is guaranteed that there are infinitely many red points and infinitely many blue points. Each line contains at least one red point and at least one blue point from $S$. Consider a triangle formed by three elements of $S$ located on three distinct lines. If two of the vertices of the triangle are red, there must exist a blue point, not one of the vertices, either inside or on the boundary of the triangle. Similarly, if two of the vertices are blue, there must exist a red point, not one of the vertices, either inside or on the boundary of the triangle.