In lecture we discussed the non-parallel lines / triangle problem. Specifically,

Question

In lecture we discussed the non-parallel lines / triangle problem. Specifically, n lines in the plane which satisfy this requirement: No two of the lines are parallel, and no three of the lines intersect at a single point. (1) form exactly C(n, 3) triangles. We outlined the proof by induction, but we did not show the algebra required in the inductive step. In this question you will demonstrate that you understand the algebra required in the inductive step. You do not need to reproduce the proof shown in lecture; you just need to answer the following three questions:

(a) If there are k lines in the plane satisfying (1), how many new triangles are formed when the (k + 1)-st line satisfying (1) is added. Justify your answer.

(b) If there are k + 1 lines in the plane satisfying (1), how many new triangles are formed when the (k + 2)-nd line satisfying (1) is added. Justify your answer.

(c) Assume k lines in the plane satisfying (1) form C(k, 3) triangles. (This is the inductive hypothesis in the proof shown in lecture.) Calculate the total number of triangles in the plane after the (k + 2)-nd line is added, by summing C(k, 3) with your answers in (a) and (b). Show all of your calculations. You will need to convert combinations into their factorial form in order to answer this question.

Explanation / Answer

a) Since the conditions are met for (k+1)th line that none of two lines are parallel and no three lines intersects at point

Number of Triangles with (k+1) points = (k+1)C3 = (k+1)(k)(k-1)/6 = (k^3-k)/6

Number of Triangles with k points = kC3 = k(k-1)(k-2)/6 = (k^3 - 3k^2 + 2k)/6

Number of Triangles Added = 3k^2/6 - 3k/6 = 0.5(k^2-k)

Hence the addition of (k+1)th line will add 0.5(k^2-k) more triangles

For justifying case, lets take k=3

3C3 = 1

adding an extra line will make (k+1) = 4, number of triangles = 4C3 = 4 (new triangles added = 4 - 1 =3)

Hence the answer 0.5(k^2 -k) = 0.5(3^2 - 3) = 3, which matches

Hence the answer is correct

b) Since the conditions are met for (k+2)th line that none of two lines are parallel and no three lines intersects at point

Number of Triangles with (k+2) points = (k+2)C3 = (k+2)(k+1)(k)/6 = (k^3+ 3k^2 + 2k)/6

Number of Triangles with (k+1) points = (k+1)C3 = (k+1)(k)(k-1)/6 = (k^3 -k)/6

Number of Triangles Added = 3k^2/6 + 3k/6 = 0.5(k^2+k)

Hence the addition of (k+2)th line will add 0.5(k^2+ k) more triangles

For justifying case, lets take k=3

3C3 = 1

adding an extra line will make (k+1) = 4, number of triangles = 4C3 = 4

adding an extra line will make (k+2) = 5, number of triangles = 5C3 = 10 (new triangles added = 10 - 4 =6)

Hence the answer 0.5(k^2 + k) = 0.5(4^2 + 4) = 10, which matches

Hence the answer is correct

c)

Answer to first part = (K+1)C3 - KC3

Answer to second part = (K+2)C3 - (K+1)C3

Using properties of addition

Total number of triangles after adding (K+2)nd line = 0.5(k^2 -k ) + 0.5(k^2 + k) = k^2

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.