1
$\begingroup$

Consider $n$, with $n > 2$, points on a plane, between which there are no collinear $3$ points. Determine the maximum number of points of intersection of these lines.

Attempt: To determine a line, we must choose two distinct points, which can be done in $\displaystyle \binom{n}{2}$ ways. The number of lines will then be given by $\displaystyle r= \binom{n}{2}$.

Knowing that two lines have at most $1$ point of intersection between them, we will choose $2$ lines from the $r$ possibilities of formation $\displaystyle \binom{r}{2}$. However, as there are possibilities for the lines to intersect, forming, as point(s) of intersection, the points that were counted in their formation, we will be counting these same points several times: for example: the line $r_1$ can pass through the point $2 $ contained in the line $r_2$; the line $r_3$ intersects the line $r_1$ and $r_2$ passing through the point $1$ and $2$ contained in the line $r_1$ and $r_2$, respectively; and so on. That is, we will take the count of $n-1$ points from $2$ straight:

$$\binom{r}{2} - \binom{n-1}{2}$$

The answer is $\displaystyle \binom{r}{2} - n \binom{n-1}{2} + n$, but I would like to know my error and how to proceed.

$\endgroup$

1 Answer 1

1
$\begingroup$

Indeed, the number of lines is $r = \binom{n}{2}$.

It follows that $\binom{r}{2}$ is the total number of intersections (without eliminating double counting).

We can then proceed to determine the number of times each of the $n$ points is counted as an intersection. Through each point, there are $n-1$ lines and any combination of two has its intersection at that same point. So, every point has been counted $\binom{n-1}{2}$ times. In other words, there are $\left[\binom{n-1}{2} - 1\right]$ redundant counts per point.

Subtracting all of these double counts yields \begin{align} \text{unique intersections} &= \text{total} - \text{double counts}\\ &= \binom{r}{2} - n \cdot \left[\binom{n-1}{2} - 1\right]\\ &= \binom{r}{2} - n \binom{n-1}{2} + n \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .