182 11. Combinatorics in Geometry
parallel and no three going through the same point, then you invariably
get 11 regions. In fact, we’ll have a similar experience for any number of
lines (check this in Figure 11.5).
FIGURE 11.5. Four lines determine 11 regions, five lines determine 16.A set of lines in the plane such that no two are parallel and no three
go through the same point is said to bein general position. If we choose
the lines “randomly,” then accidents like two being parallel or three going
through the same point will be very unlikely, so our assumption that the
lines are in general position is quite natural.
Even if we accept that the number of regions is always the same for a
given number of lines, the question still remains, what is this number? Let
us collect our data in a little table (including also the observation that 0
lines divide the plane into 1 region, and 1 line divides the plane into 2):
0 1 2 3 4
1 2 4 7 11
Staring at this table for a while, we observe that each number in the
second row is the sum of the number above it and the number to the left of
it. This suggests a rule: Thenth entry isnplus the previous entry. In other
words:If we have a set ofn− 1 lines in the plane in general position, and
add a new line (preserving general position), then the number of regions
increases byn.
Let us prove this assertion. How does the new line increase the number
of regions? By cutting some of them into two. The number of additional
regions is just the same as the number of regions intersected.
So, how many regions does the new line intersect? At a first glance, this
is not easy to answer, since the new line can intersect very different sets
of regions, depending on where we place it. But imagine walking along the
new line, starting from very far away. We get to a new region every time we
cross a line. So the number of regions the new line intersects is one larger
than the number of crossing points on the new line with other lines.
Now, the new line crosses every other line (since no two lines are parallel),
and it crosses them in different points (since no three lines go through the
same point). Hence during our walk, we seen−1 crossing points. So we
seendifferent regions. This proves that our observation about the table is
true for everyn.