Wednesday 7 August 2019

Lines and Triangles

Consider the following problem as shown in Figure 1.


Figure 1

I just stumbled upon this problem, or rather a generalisation of this problem, and thought its solution was worthy of a mention. The solution was quite simple once I read it. Let's first review what the diagram shows. There are three parallel lines (labelled 1, 2 and 3) and another five non-parallel lines (labelled 4 to 8) that intersect with each other and also with the parallel lines. No three lines pass through a single point. How many triangles are formed?

Let's break the problem into two parts. Firstly let's deal with the five non-parallel lines. It takes three lines to make a triangle and so there are$$ \binom 5 3 = \binom 5 2 =\frac{5 \times 4}{2 \times 1}= 10 \text { possible combinations}$$So the five non-parallel lines form 10 triangles with each other. The three parallel lines can each be linked to a pair of non-parallel lines. This becomes:$$ \binom 5 2 \times 3 = 10 \times 3 = 30 \text{ possible combinations}$$So in total there are \(10 + 30 = 40\) triangles formed.

Generalising this, if there are \( n \) non-parallel lines and \(m\) parallel lines then:$$\text {The number of triangles formed is given by } \binom n 3 + \binom n 2 \times m$$Of course if none of the lines are parallel then \(m=0\) and the expression simplifies accordingly. It's interesting to count the number of points as well (shown in Figure 2):


Figure 2

The intersection of the lines produces 25 points, which I dutifully counted and labelled. If the points are taken in pairs, then each pair will generate a line with the result that there will be \( \binom {25} 2 = \frac {25 \times 24}{2 \times 1}=300\) lines which is clearly not the case because many of the lines are the same as others due to the large number of collinear points. 

However it can be noted that when two lines intersect, a point is created and so the following expression arises:$$ \binom 5 2 + 5 \times 3 = 10 + 15 =25 \text { which confirms my manual count}$$This can be generalised to:$$ \text {The number of points is given by }\binom n 2 + n \times m$$

No comments:

Post a Comment