Consider $n$ lines in the plane in general position, that is, there are not three of the $n$ lines that pass through the same point. Determine if it is possible to label the $k$ points where these lines are inserted with the numbers $1$ through $k$ (using each number exactly once), so that on each line, the labels of the $n-1$ points of that line are arranged in increasing order (in one of the two directions in which they can be traversed).
Problem
Source: Mathematics Regional Olympiad of Mexico Center Zone 2018 P3
Tags: combinatorial geometry, combinatorics
plagueis
01.08.2022 06:30
Proposed by Oriol Solé Pi
ShyMathGuy
03.08.2022 07:45
Beautiful problem
Yes it is posible.
Let $S$ be the set formed by the $k$ points in which the $n$ lines intersect. Let us take a line $\ell_1$ such that neither $\ell_1$ nor any of the lines parallel to $\ell_1$ pass through two points of $S$. Let $\ell_2$ be a line perpendicular to $\ell_1$. Let us assign a direction to the $\ell_2$ and consider, for each point $P \in S$, the projection of $P$ onto $\ell_2$. Then, we label each point on $\ell_2$ with a number from 1 to $k$, in an increasing way following the direction of the line. We will show that by labeling each point $P \in S$ with the same number with which we labeled its projection on $\ell_2$ the conditions of the problem are satisfied.
Since there is no line parallel to $\ell_1$ that passes through two points in $S$, then there are no two points in $S$ whose projection on $\ell_2$ coincides, and therefore there are no two points in $S$ with the same number. On the other hand, to see that in each of the $n$ lines, the labels of the points of the line are ordered, it is enough to notice that projecting the points on a line doesn't modify the order that they have between them, which concludes the problem.
Attachments:
