Maths Olympiad Prep

Library / Silk Road Mathematics Competition competition problems /23 of 25

Silk Road Mathematics Competition competition problems

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 l1∈Ll_1 \in L is bounding the line l2∈Ll_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 l′l' such that the following two conditions are hold simultaneously:
1) the line ll is bounding the line l′l';
2) the line l′l' is not bounding the line ll.

Solution

Assume the contrary, i.e. there aren't lines ll and l′l', satisfying the conditions 1) and 2).
Let's choose an arbitrary l∈Ll \in L. There are two points a,b∈la, 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 l′l', 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 l′l'.
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. xRy⇒x≠y&yRxx\mathcal{R}y \Rightarrow x \neq y \& y\mathcal{R}x. Suppose that for any point a∈Aa \in A there are exactly two points b∈Ab \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 a0Ra1Ra2R…anRa0a_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}, 2≤i≤n−12 \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 a0Ra1Ra2R…anRa0a_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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.