Maths Olympiad Prep

Library / /26 of 29

Geometry Difficulty 6.9 National olympiad Prove it Silk Road Mathematics Competition

A family LL of 20062006 lines on the plane is given in such a way that it doesn't contain parallel lines and it doesn't contain three concurrent lines. We say that the line l1Ll_1 \in L is bounding the line l2Ll_2 \in L, if all intersection points of the line l2l_2 with other lines from LL lie on the one side of the line l1l_1. Prove that in the family LL there are two lines ll and ll' such that the following two conditions are hold simultaneously:
1) the line ll is bounding the line ll';
2) the line ll' is not bounding the line ll.

Solution

Assume the contrary, i.e. there aren't lines ll and ll', satisfying the conditions 1) and 2).
Let's choose an arbitrary lLl \in L. There are two points a,bla, b \in l such that a,ba, b are intersection points of ll with lines from LL, and all intersection points of the line ll with lines from LL lie on the segment [a,b][a, b]. This [a,b][a, b] is called a big segment (of the line ll).
There is another line, say ll', that passes through the endpoint aa of the big segment [a,b][a, b]. Then, by the assumption, this aa will be an endpoint of the big segment of the line ll'.
Denote by AA the set of all endpoints of big segments; and if [a,b][a, b] is a big segment then we write aRbaRb and say that aa and bb are in the relation R\mathcal{R}.
Lemma 1. Let R\mathcal{R} be an irreflexive, symmetric relation on the finite set AA, i.e. xRyxy&yRxx\mathcal{R}y \Rightarrow x \neq y \& y\mathcal{R}x. Suppose that for any point aAa \in A there are exactly two points bAb \in A such that aRba\mathcal{R}b. Then AA is partitioned into a finite R\mathcal{R}-cycles of the length 3\ge 3.
Proof. is well-known.
But in our situation there is an unique R\mathcal{R}-cycle of the odd length.
Lemma 2. R\mathcal{R}-cycles have odd lengths.

SOLUTIONS
Proof. Let a0Ra1Ra2RanRa0a_0\mathcal{R}a_1\mathcal{R}a_2\mathcal{R}\dots a_n\mathcal{R}a_0 be a cycle of the length n+1n+1 and a=a0,b=a1a=a_0, b=a_1. The points aia_i and ai+1a_{i+1} lie on different sides of the line labl_{ab}, 2in12 \le i \le n-1, since any two big segments must intersect. Also, ana_n and a2a_2 should lie on the same side, otherwise the big segments [an,a0][a_n, a_0] and [a1,a2][a_1, a_2] would not intersect. So, nn is even. \square
Lemma 3. There is an unique R\mathcal{R}-cycle.
Proof. Let a0Ra1Ra2RanRa0a_0\mathcal{R}a_1\mathcal{R}a_2\mathcal{R}\dots a_n\mathcal{R}a_0 be a cycle. Assume that there exists a big segment [b,c][b, c] outside this cycle. The line of segment [b,c][b, c] divides the plane into 2 semiplanes. Since big segments should intersect, adjacent (by R\mathcal{R}) points of that cycle should lie on a different semiplanes. But it is impossible, because cycle contains an odd number of points. \square
Lemmas give a contradiction with assumptions, because 20062006 is even number.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.