Let $ k$ and $ n$ be integers with $ 0\le k\le n - 2$. Consider a set $ L$ of $ n$ lines in the plane such that no two of them are parallel and no three have a common point. Denote by $ I$ the set of intersections of lines in $ L$. Let $ O$ be a point in the plane not lying on any line of $ L$. A point $ X\in I$ is colored red if the open line segment $ OX$ intersects at most $ k$ lines in $ L$. Prove that $ I$ contains at least $ \dfrac{1}{2}(k + 1)(k + 2)$ red points. Proposed by Gerhard Woeginger, Netherlands
Problem
Source: IMO Shortlist 2008, Geometry problem 5, German TST 1, P2, 2009
Tags: geometry, point set, combinatorial geometry, lines, IMO Shortlist
bertram
10.07.2009 20:08
Let $ l$ be the line with minimal distance to $ O$ and $ P$ be the point of$ I$ on $ l$ that minimizes $ OP$. A standard argument shows that $ OP$ cannot intersect any line of $ L$. This solves $ k=0$. The rest can be done by induction over $ k$: Sorting the points $ P_1,P_2,\dots,P_{n-2}$ of $ L%Error. "capI" is a bad command.
\setminus\{P\}$, it is obvious that the segment $ OP_i$ can cut at most $ i$ lines (Induction over $ i$). Then, remove $ l$; the induction hypothesis asserts that there are at least $ \frac{1}{2}k(k+1)$ points $ P$ so that $ OP$ intersects at most $ k-1$ lines of $ L$. Adding $ l$, $ P,P_1,\dots,P_k$ back, we see that there must be $ \frac{1}{2}k(k+1)+k+1 = \frac{1}{2}(k+1)(k+2)$ red points.
Overall not that difficult, especially for a G5...
feliz
01.08.2009 23:05
This one can be done using the dual principle (i.e., changing the words "point" and "line"). We transform each point in its polar line wrt a circle centered in $ O$. Using the fact that $ a \in B \Leftrightarrow b \in A$ and an approximation of $ O$ and $ X$ makes $ x$ moves away of $ O$, one can prove the following: $ OX$ intersects at most $ k$ lines in $ L \text{ } \Leftrightarrow$ the half plane determined by $ x$ which does not contain $ O$ has at most $ k$ points in $ L'$, the set of the poles of the lines in $ L$. In a formal point of view, the difficulty of the problem is the same after the transformation. However, I find points more intuitive than lines, which allowed me to get the solution easily.
Zhero
30.03.2011 15:48
We will keep $k$ fixed and induct on $n$. For the base case $n=k+2$, we note that there are $\binom{n}{2} = \binom{k+2}{2}$ points here, so it is sufficient to show that for all points of intersection $X$, the open segment $OX$ intersects no more than $n-2$ lines. But this is obvious, as there are only $n$ lines, $X$ lies on two of them, and $X$ does not lie on the open segment $OX$.
Suppose that for some $n$ and $k$, the result is true. Consider any $n+1$ lines $\ell_1, \ell_2, \ldots, \ell_{n+1}$. Applying the inductive hypothesis to $\ell_1, \ell_2, \ldots, \ell_n$, we can find points $\mathcal{X} = X_1, X_2, \ldots, X_{\binom{k+2}{2}}$ such that the open segments $OX_1, OX_2, \ldots, OX_{\binom{k+2}{2}}$ each intersect at most $k$ lines.
Let $\mathcal{Y}$ be the set of all $X_i$ such that $OX_i$ intersects exactly $k$ lines before $\ell_{n+1}$ is added and $\ell_{n+1}$ intersects $OX_i$. It is clear that for $X \notin \mathcal{Y}$, $X \in \mathcal{X}'$. For each $Y \in \mathcal{Y}$, let $f(Y)$ be the intersection of $OY$ and $\ell$. Because each ray emanating from $O$ can contain at most one element of $\mathcal{Y}$, $f$ is injective, so $f(\mathcal{Y})$ has at least $|Y|$ elements. No three lines are concurrent and $Of(Y)$ intersects at most $k$ lines after $\ell_{n+1}$ is added, so $f(\mathcal{Y}) \subseteq \mathcal{X}'$. Hence, \[ |\mathcal{X}'| = |\mathcal{X} \backslash \mathcal{Y}| + |\mathcal{Y}| \geq |\mathcal{X}| - |\mathcal{Y}| + |\mathcal{Y}| \geq |\mathcal{X}| \geq \binom{k+2}{2}\]
by the inductive hypothesis, so we are done.
JuanOrtiz
21.04.2015 03:16
I use induction on $k$, the base case is easy by considering a corner of the region of $O$. Now assume the statement is true for $k-1$, I prove it for $k$. Consider a point $Q$ that is a corner of the region in which $O$ is in. In a line through $Q$ there are at least $k+1$ good intersection points of this line with other lines. If we forget about this line, by induction there are $1+...+k$ good points $P$ (such that $OP$ cuts at most $k-1$ lines), and adding this line back adds at most one intersection point to the segment $OP$ to them, so they are still good. All in all we have $1+...+(k+1)$ good points so we are done.
iman007
12.07.2021 20:42
fix $n$ and apply induction on $k$. the base case for $k=0$ is obvious consider the intersection of the nearest lines to $O$. consider that the statement is true for $k$ we will prove for $k+1$ now note that if we consider a point $X$ on a line $l$ such that no line intersects $OX$ then the nearest $k+1$ points near to $X$ on the line $l$ are red. if you don't consider so after removing $l$ there are $\binom{k+2}{2}$ and after restoring $l$ there are $k+2$ new red points including $X$. so in general we have $\binom{k+3}{2}$.$\blacksquare$
JAnatolGT_00
21.07.2022 13:24
Let $\ell$ be the nearest to $O$ line from $L$ and $\ell \cap I=\left\{ X_1,X_2,...,X_{n-1}\right\}$ with $|OX_i|\leq |OX_{i+1}|$ for every $i.$ Claim. Open segment $OX_i$ intersects at most $i-1$ line from $L.$ Proof. Suppose the opposite, so $OX_i$ intersects $i$ lines and in particular it intersects line $\ell '$ such that $Y= \ell \cap \ell '\notin \bigcup_{t=1}^{i-1}X_t.$ If $Z=OX_i \cap \ell '$ we get the contradiction with $$|OY|\geq |OX_i|\implies \angle OYX<90^\circ \implies d(O,\ell ')=|OY|\cdot \sin \angle OYZ<|OY|\cdot \sin \angle OYX_i=d(O,\ell )\text{ } \Box$$ Now with fixed $n$ we apply induction by $k.$ By the claim $X_1$ is always red, so the base case $k=0$ follows. Now consider problem statement for $L\backslash \ell$ and $k=p,$ so there exist at least $C_{p+2}^2$ red points. After backing $\ell$ to $L$ and increasing $k$ to $p+1$ all red points are preserved and by claim all points $X_1,X_2,...,X_{p+2}$ are red, so totally there are at least $C_{p+3}^2$ red points $\blacksquare$