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$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.