Given n lines in general position in the plane, which means that any two lines h

Question

Given n lines in general position in the plane, which means that any two lines have a common point and no point of the plane belongs to more than two lines. (a) Use mathematical induction to prove tha the lines divide into N = {(n+1) choose 2}+1 regions, for every n>= 1. (b) Use mathematical induction to prove that the map of these N regions can be colored with two colors in such a way that no regions with a common border line get the same color (in other words, any two regions obtaining the same color share at most one common boundary point).

Explanation / Answer

First, if n = 0, we note that if zero lines are drawn on the plane, there is a single region: the whole plane, so the statement is true if n = 0 since (02 + 0 + 2)/2 = 1. Next, assume that no matter how you draw k lines on the plane, consistent with the conditions of the problem, that there are exactly (k 2 + k + 2)/2 regions formed. Consider a similar con?guration of k + 1 lines. If we choose one of them and eliminate it, there will, according to the induction hypothesis, be (k 2 + k + 2)/2 regions. When we look at the line we temporarily eliminated, since it is not parallel to any of the lines, it must intersect all of them: that makes k intersections. None of these intersections are at the same point on the new line, or otherwise there would be three lines intersecting at a point, which is not allowed according to the conditions of the problem. The points of intersection thus divide the new line into k + 1 segments, each of which lies in a different one of the (k 2 + k + 2)/2 regions formed by the original k lines. That means that each of these k + 1 segments divides its region into two, so the addition of the (k + 1) st line adds k + 1 regions. Thus there are now: (k 2 + k + 2)/2 + (k + 1) regions in the new con?guration. A tiny bit of algebra shows that this is equivalent to ((k + 1)2 + (k + 1) + 2)/2 regions, which is what we needed to show. Based on this idea, can you see how to ?nd a formula for the number of regions into which space will be divided by n planes where the planes are in “general position”, meaning that none are parallel, no three of them pass through the same line, and no four of them through the same point? Hint: what does the intersection of the (k + 1)st plane with k planes look like? With zero lines, you can obviously do it; in fact, one color would be suf?cient. If you can successfully 2-color the plane with k lines, when you add the (k + 1) st line, swap the colors of all the regions on one side of the line. This will provide a 2-coloring of the con?guration with k + 1 lines. (In fact, for this problem, there is no real need to have the lines in general position: some can be parallel, and multiple lines can pass through a point, and the proof will continue to work.)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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