Maths Olympiad Prep

Library / /9 of 13

Geometry Difficulty 6.0 National olympiad Prove it South Africa

For which integers n2n \ge 2 is it possible to draw nn distinct straight lines in the plane in such a way that there are at least n2n-2 points where exactly three of the lines intersect?

Solution

For n=2n=2, any two lines satisfy the condition, and for n=3n=3, we can take any three lines passing through a common point.

For n=4n=4, there is no feasible choice of four lines: suppose there are two points where exactly three lines meet. At most one of the lines can pass through both, so we need at least 1+2×2=51+2 \times 2 = 5 lines.

The same argument shows that it is impossible for n=5n=5: suppose there are three points where exactly three lines meet. If one line passes through all of them, we still require two further lines through each of the three, and no two of them can coincide. This already gives us 1+3×2=71+3 \times 2 = 7 lines. If the three points do not lie on a line, then there can be at most one line passing through any two of them, leaving us with at least one more line through each of the points that does not pass through any of the others. This gives us a total of at least 3+3=63+3=6 lines.

There is a possible configuration for every n6n \ge 6: for n=6n=6, we can take the (extended) sides and diagonals of any (non-degenerate) quadrilateral. For larger values of nn, we use an inductive construction: if we start with the sides and diagonals of a quadrilateral for which opposite sides are not parallel, then there are also two intersections of exactly two lines (namely the opposite sides). In each further step, we add a line through one of the intersections of exactly two lines, chosen in such a way that it does not pass through any of the other intersections that were obtained previously. This ensures that we get new intersections of exactly two lines with each step, and the number of points where exactly three lines meet increases by one. Thus the number of points where three lines meet will be (exactly) n2n-2 when the nn-th line is drawn.

We conclude that it is possible to draw nn lines in a suitable way for all n4,5n \ne 4, 5.

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.