Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was recently working through the IB HL textbook and I came across two interesting problems.

Exercise 8E

Question 18.

Line A contains 10 points and line B contains 7 points. If all points on line A are joined to all points on line B, determine the maximum number of points of intersection between A and B.

Question 19.

10 points are located on [PQ], 9 on [QR] and 8 on [RP]. All possible lines connecting these 27 points are drawn. Determine the maximum number of points of intersection of these lines which lie within triangle PQR.

The answer for the first question is relatively easy to get. However it is the solution which the book provides, combined with the fact that it works which perplexes me. The answer for 18 is $$\binom{10}{2}\binom{7}{2}=945$$

My approach to the problem was: if you draw lines between the first 2 dots of the 7 with all the other 10, the number of intersections is 45. When you draw lines from the third dot you get 90 (a multiple of 45). As it turns out this is merely an extract of the multiplications table. Once you add up all the numbers you get 945 (or to shorten the calculations I just took 45 multiplied by 21)

My question is how is combinations related to this question, and if I were to see this question for the first time, how would I go about approaching it to get the solution provided in the book.

Secondly, the answer to 19 is $$\begin{align*} c=\binom{10}{2}\binom{9}{2}&+\binom{10}{2}\binom{8}{2}+\binom{9}{2}\binom{8}{2}+\binom{10}{2}\binom{9}{1}\binom{8}{1}+\\ &+\binom{10}{1}\binom{9}{2}\binom{8}{1}+\binom{10}{1}\binom{9}{1}\binom{8}{2} \end{align*}$$ How did they get the last 3 components of the equation? I get where they come from, but not how to get them.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Question 18: Pick two of the points on line A, say $p$ and $q$ and two on line B, say $r$ and $s$. Of the lines $\overline{pr},\overline{ps},\overline{qr}$, and $\overline{qs}$, only one pair $-$ either $\overline{pr}$ and $\overline{qs}$, or $\overline{ps}$ and $\overline{qr}$ $-$ produces a point of intersection between lines A and B. Conversely, every point of intersection between lines A and B is produced in this way. That is,

for every quadruple of points consisting of two from line A and two from line B you get exactly one point of intersection between lines A and B, and every point of intersection between lines A and B is obtained in this way.

Now some of the quadruples could produce the same point of intersection between lines A and B, so I can’t say that there are therefore exactly as many points of intersection between lines A and B as there are ways to choose two points from line A and two from line B. I can say, however, that there are at most as many points of intersection between lines A and B as there are ways to choose two points from line A and two from line B.

There are $\binom{10}2$ ways to choose two of the ten points from line A and $\binom72$ ways to choose two of the seven points from line B, so the number of ways to pick two from each line is $$\binom{10}2\binom72,$$ so this is also the maximum possible number of points of intersection between lines A and B.

Question 19: The reasoning is the same, but there’s a new possibility for getting a point of intersection: pick two points on one of the lines and one point on each of the other two lines. Say $p$ and $q$ are on the same line, and $r$ and $s$ are on the other two lines. Then once again exactly one of the pairs $\{\overline{pr},\overline{qs}\}$ and $\{\overline{ps},\overline{qr}\}$ will intersect within the triangle. The number of ways of picking two points on $\overline{PQ}$ and one each on the other two lines is $$\binom{10}2\binom91\binom81,$$ and the other three terms are formed similarly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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