Let $l_1,l_2,l_3,...,L_n$ be lines in the plane such that no two of them are parallel and no three of them are concurrent. Let $A$ be the intersection point of lines $l_i,l_j$. We call $A$ an "Interior Point" if there are points $C,D$ on $l_i$ and $E,F$ on $l_j$ such that $A$ is between $C,D$ and $E,F$. Prove that there are at least $\frac{(n-2)(n-3)}{2}$ Interior points.($n>2$) note: by point here we mean the points which are intersection point of two of $l_1,l_2,...,l_n$.
Problem
Source: Iranian Math Olympiad(Second Round 2016)
Tags: combinatorics
05.05.2016 22:26
I may be wrong but , isn't any intersection point here an "interior point"??
05.05.2016 23:13
First Case: $(n>3)$ First of all let a point be an "Exterior point" if it's not an "Interior Point". Also consider the line $l_i$ and a point $A$ on it. We call $A$ an "Endpoint" for $l_i$ if there are no two points on $l_i$ such as $B,C$ such that $A$ is between $B,C$. Obviously there are exactly two "Endpoints" for each line. Now let $A_1,A_2,...,A_k$ be all of the "Exterior" points. Our purpose here is to prove that $k \le 2n-3$ so assume the contrary:"let $k>2n-3$". Consider an arbitrary exterior point $A_1$ and let it be the intersection point of $l_u,l_v$. We want to prove that $A_1$ is Exterior for at least one of $l_u,l_v$. Assume the contrary:"Let $A_1$ be Interior for both of $l_u,l_v$". Thus there are points $B,C\in l_u$ and $D,E \in l_v$ such that $A_1$ is between $B,C$ and $D,E$. According to definition of an Interior point here $A_1$ is an interior point and this is a contradiction because we assumed that $A_1$ is an Exterior point. Now let $T \subseteq \{A_1,A_2,...,A_n\}$ such that for every $A_j \in T,A_j$ be an Endpoint for both of the lines which $A_j$ is their intersection point. Let $S$ be the set of the rest of $A_1,A_2,...,A_n$ which are not in $T$. We want to prove that $2|T|+|S| \le 2n$. Let $G$ be a bipartite graph such that one part of its vertices$(X=\{x_1,x_2,..,x_n\})$ represent $l_1,L_2,...,l_n$ and the other part$(Y=\{y_1,y_2,...,y_k\})$ represent $A_1,A_2,...,A_k$. Here we connect $x_i,y_j$ iff $A_j$ be an endpoint for $l_i$. Let $\Delta$ be the number of edges of $G$. We want to calculate $G$ in two ways. First of all every $y_i$ is connected to at most two of $x_1,x_2,...,x_k$. Because every line $l_i$ has exactly two Endpoints and at most two of $A_1,A_2,...,A_k$ are Endpoints of $l_i$. So we conclude that: $\Delta \le 2n$. On the other hand if $A_i \in T$ then $x_i$ is connected two exactly two of $y_1,y_2,...,y_n$ according to the conditions of choosing the elements of $T$. Otherwise if $A_i \in S$ then $x_i$ is connected to exactly one other of $y_1,y_2,...,y_n$ again according two the conditions of choosing the element of $S$. Now we will have: $\Delta=2|T|+|S|$. Now we conclude: $2|T|+|S| \le 2n$. From the other hand we assumed that: $|S|+|T| \ge 2n-2$. According to the following inequalities we conclude that: $|T| \le 2$. Now we want to prove that $|T| \ge 3$. Let $P$ be the set of points which are intersection points of two of $l_1,l_2,...,l_n$. Consider the convex hull of the points in $P$. let $C$ be the polygon made by this convex hull. Since all of the elements of $P$ are not on the same line we conclude that $C$ has at least three different vertices. We want to prove that every point on $C$ is an element of $T$. Consider point $Q$ on $C$ and let it be the intersection point of $l_a,l_b$. Here we want to say that $Q$ is an Endpoint for both of $l_a,l_b$. Consider the part of $l_a$ which is not in the convex hull(specially is not in $C$). According to definition of the convex hull there's no point on that part of $l_a$. So each point on $l_a$(different from $Q$) lies on the same side of $Q$. Thus $Q$ is an Endpoint for $l_a$ with the same argument we can say that it is also an Endpoint for $l_b$. Now $Q$ is an Exterior point and it's an endpoint for both of $l_a,l_b$ thus it is an element of $T$ which gives us $|T| \ge 3$ since every point on $C$ is an element of $T$ and there are at least three points on $C$. Finally this is a contradiction because we had that $|T| \le 2$. So we conclude that $|S|+|T| \le 2n-3$ and this is what we wanted to prove. Second case: $n=3$: this case is obvious by a simple checking. Note: Since there are $\frac{n(n-1)}{2}$ points and at most $2n-3$ of them are "Exterior" thus at least $\frac{n(n-1)}{2}-(2n-3)=\frac{(n-2)(n-3)}{2}$ of them are "Interior".
12.05.2016 13:40
http://s000.tinyupload.com/?file_id=64246544323528695082