South African Mathematics Olympiad Third Round

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

For $n=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\times 2=5$ lines.

The same argument shows that it is impossible for $n=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\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=6$ lines.

There is a possible configuration for every $n\ge 6$: for $n=6$, we can take the (extended) sides and diagonals of any (non-degenerate) quadrilateral. For larger values of $n$, 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) $n-2$ when the $n$-th line is drawn.

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