If n $\geq$ 2 lines are drawn in the plane, they divide it into a number of regions. Assume that no two lines are parallel and that no three lines meet at a single point. Show that it is possible to assign a non-zero integer to each region so that the sum of the integers on either side of each line is zero.

This might be hard to explain what I'm thinking, but here goes...

Since my base case is 2 lines, that means there is 1 intersection, and 4 quadrants to that 1 intersection. And the summation of each side is 0.

If I $\underline{assume}$ that a line intersecting another line creates 4 quadrants, and the summation of each side of the line $\underline{can}$ equal 0, can my inductive step expand on the fact that every new line crosses every other line, and creates intersections with 4 quadrants?

Does this sound close? Do intersections and quadrants have nothing to do with this question? :(

Hints please!


The assumption of having non-parallel lines is not necessary, as long as you already have a valid solution for $n \geq 2$ lines and you want to extend it to $n+1$ lines. (So you cannot start with 2 parallel lines, but you can consider the lines in any order so if some two of them are not parallel, then you can start with them). Clearly for $n=2$, you can come up with a solution by assigning $1$ and $-1$ clockwise alternating between quadrants defined by the two lines, if the 2 lines are not parallel.

So now assume you have a solution for $n$ lines. When you add one more line, then assuming it doesn't intersect any two lines in a common intersection point, then this line will split some regions into two regions and leave all other regions the same. So just double all the integers you had before adding the new line, and then for each split region, split the integer in half between the two split regions for all regions except for two, and for the last two split regions, split the integer in half between the two subregions and then add a new integer to one subregion and subtract the new integer from the other subregion, in such a way that all the integers on each side of the new line add up to zero. The only remaining details are to show this is always possible, so that both sides of the new line each add up to $0$, and that since each split region is assigned two integers that add up to the original integer for the region, and every other line has both subregions of a newly split region either both on one side or both on the other, your property of having each side of a line add up to zero is preserved. And finally, since there must be at least 2 split regions, that you can assign the integers for the subregions of each of the 2 last split regions so that none of the integers for the 4 subregions are zero.


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.