Find the smallest natural number $n$ that the following statement holds : Let $A$ be a finite subset of $\mathbb R^{2}$. For each $n$ points in $A$ there are two lines including these $n$ points. All of the points lie on two lines.
Problem
Source: Iranian National Olympiad (3rd Round) 2002
Tags: analytic geometry, combinatorics proposed, combinatorics
02.01.2007 11:33
Old but nice. The smallest desired number is $6$. Let $E$ be the set of the $6$ points with coordinates $(0,0),(2,0),(2,2),(0,2),(0,1),(1,1).$ It is easy to verify that any subset of $5$ points from $E$ can be covered by two lines, but $E$ cannot be covered by two lines (since there is no four collinear points in $E$, any covering of $E$ by two lines would separate the six points into three points of collinear points. The unique triple of collinear points from $E$ which contain $(0,1)$ is $(0,0),(0,1),(0,2)$. Therefore the second line has to cover the three other points which are not collinear...). Now, we prove that $n=6$ has the desired property. Let $E$ be any set of at least $6$ points in the plane, such that any subset of $6$ points from $E$ can be covered by two lines. Let F be any subset of $E$ with $6$ points. From the pigeon-hole principle, at least three points from $F$, and then from $E$, must be collinear. Say $A,B,C$ are collinear, and belong to the line $\Delta$. If $E$ contains at most two points which are not on $\Delta$, we are done. Otherwise, let $X,Y$ be two points from $E$ which are not on $\Delta$, and let $\Delta '$ be the line $(XY)$. For any point $M$ in $E$ which is not $X$ or $Y$ and which does not belong to $\Delta$, we know that the set formed by $A,B,C,X,Y,M$ can be covered by two lines. If none of these lines is $\Delta$ then the line which covers $A$ cannot cover $B$ or $C$. Thus the other line must cover $B$ and $C$ so that this is $\Delta$, a contradiction. Therefore, one of the line is $\Delta$. It follows that the other line must cover $X,Y,M$, which forces this second line to be $\Delta '$ and $M \in \Delta '$. Thus, any point from $E$ belongs either to $\Delta$ or $\Delta '$, which proves that $E$ can be covered by two lines, and we are done. Pierre.
02.01.2007 12:02
Great work !!! Well done