Suppose you have a circle with n points lying on the perimeter of the circle and lines connecting all of the points. There would be a total of lines connecting the points (from the obvious recurrence , which was famously simplified into that closed form by young Carl Friedrich Gauss). The mission is to find the precise maximum number of areas that the circle can be divided into (f(n)) given the number of points n.
The obvious approach is to draw some circles and see what you get. n=0 yields a boring circle, a single area. n=1 has one point but l(1)=0 (that is to say, there are no lines), so there is still just one undivided area. When f(2)=2 because there is a single line dividing it into two areas. f(3)=4, f(4)=8, and f(5)=16. It is tempting to declare that . But can you prove it? Hint: f(6)=31.
It will later be useful to know what happens to a set of areas already divided by x lines when you run another line from one end to the other, crossing x lines (see the example where x=2). This is complex because if the x lines intersect eachother then we could chose to insert the new line such that it hits the intersection point, resulting in fewer new areas being generated by the division. However, there will generally be a path for the new line such as line {b} which does not involve more than two lines intersecting at any given point (proof?), and in this case it will generally result in the creation of x+1 (in this case 3) new spaces. Hopefully with the figure and your own intuition this is obvious, but some members of the audience may desire a more rigorous proof.
And here we go. This will be an inductive proof. That is to say that we will start at an arbitrarily small example (such as f(0)=0) and then provide a formula for f(n) in terms of f(n-1).
In the figure you can see the dark lines connecting
points 1 through 4 dividing the circle into 8 total
regions (i.e., f(4)=8). This figure illustrates the inductive
step from n=4 to n=5 with the dashed lines. When the fifth point is added (i.e., when
computing f(5) using f(4)), this results
in four (n-1) new lines (the dashed lines in the diagram) being added,
which I will number 1 through 4, one for each point that they connect
to. The number of new regions introduced by the fifth point can
therefore be determined by considering the number of reginos added by
each of the 4 lines. So set i to count the lines we are adding.
Each new line can cross a number of existing lines, depending on which
point it is to (the value of i). The new lines will never cross
eachother except at the new point because they are non-coincident
lines (they contain at least one unique point, namely the other
endpoint) so they have exactly one intersection and no more.
The number of lines that each new line intersects can be determined by
considering the number of points on the "left" of the line and the
number of points on the "right" of the line. Since all existing
points already have lines between them, the number of points on the
left multiplied by the number of points on the right is the number of
lines that will be crossing the new line. For the line to point i,
there are n-i-1 points on the left and i-1 points on the right, so
a total of (n-i-1)(i-1) lines must be crossed.
In this example, the lines to i=1 and i=4 each cross zero lines,
while the lines to i=2 and i=3 each cross two lines (there are two
points on one side and one on the other).
So the recurrence can be expressed as
An interesting further proof might be the minimum number of regions
that a circle must be divided into in order to accommodate n points
in this fashion. This requires that more than two lines intersect at
a single point.Lemma
Proof
Which can be easily reduced somewhat to
But it is not obvious how to get this down to a closed form (to eliminate
the summation or the recurrence).