The possible number of intersections of n lines

258 Views Asked by At

Suppose there are $n$ lines on a plane with no $3$ lines concurrent, such that they are not all parallel. What are the possibilities for the number of intersections of these lines?

I get that the minimum number is $n-1$ and the maximum number is $n(n-1)/2$. Can we find a configuration of $n$ lines such that there are $x$ points of intersection, for any $x$ between $n-1$ and $n(n-1)/2$?

This seems to be true when $n$ is $3$ and $4$.

1

There are 1 best solutions below

2
On

When $n\ge 5$, you cannot achieve $x$ intersections, whenever $n\le x\le 2n-5$. There are other impossible values of $x$ as well. For example, when $n=6$, it is impossible to attain exactly $10$ intersections. I do not know how to characterize the complete set of possible $x$.

Suppose there are $k$ classes of mutually parallel lines, where the $i^\text{th}$ class has $n_i$ lines. Necessarily, $n_1+\dots+n_k=n$. We are also assuming $k\ge 2$. The number of intersections is $$ \binom{n}2-\binom{n_1}2-\binom{n_2}2-\dots-\binom{n_k}2 $$ I claim that, for fixed $k$, the minimum value of the above expression is attained when $n_1=n-k+1$, while $n_i=1$ for $i\in \{2,\dots,k\}$. This follows because $$ a\ge b\ge 2\implies \binom{a+1}2+\binom{b-1}2\ge \binom a2+\binom b2, $$ so if there are multiple $n_i$'s which are greater than $1$, you get get a smaller expression by decreasing the smaller one and increasing the bigger one.

Let's examine the $k=2$ case first. If $n_1=n-1$ and $n_2=1$, the number of intersections is $$ \binom n2 - \binom{n-1}2-\binom 12=n-1, $$ which is the minimum number. The second smallest possibility for $k=2$ is when $n_1=n-2$ and $n_2=2$, in which case we get $$ \binom{n}2-\binom{n-2}2-\binom{2}2=2n-4 $$ This means that we cannot achieve $x$ intersections, for any $x$ strictly between $n-1$ and $2n-4$, at least when using $k=2$. But you can show that $k\ge 3$ is no help either. For example, when $k=3$, the minimum value is $\binom{n}2-\binom{n-2}2-\binom12-\binom12=2n-3$. As $k$ increases, the minimum only increases further.