Plane division by Lines AND Circles (Problem, Analysis and Solution)
A plane can be divided by a line or circle (or both) into regions. We assume the lines go on to infinity.
There is a lot online about planes being divided by lines or circles but not BOTH!
http://mathworld.wolfram.com/PlaneDivisionbyLines.html
http://mathworld.wolfram.com/PlaneDivisionbyCircles.html
Let us Examine Lines:
Obviously 0 lines has 1 region (the plane itself)
1 line creates 2 regions.
2 lines create 4 regions.
3 lines create 7 regions.
4 lines create 11 regions.
Lets do up a table:
We can easily work out a recursive formula to work out R(N), the number of regions produced by N lines.
R(N) = R(N1) + N+1
Now we use the telescoping method to work out a general formula for N.
R(1) – R(0) = 1 R(2) – R(1) = 2 R(3) – R(2) = 3 ….................... R(N) – R(N1) = N
Now if we add both sides we get ALL the numbers cancelling except:
R(N) – R(0) =
To work out the sum to N terms, we can use the infamous Gauss' method...
S = 1 + 2 + 3 + ….....+ N S = N + N1 + …......+ 1  2S = (N+1) +(N+1)......+(N+1)
2S = N(N+1)
S = ½ N(N+1)
So R(N) – R(0) = ½ N(N+1)
R(0) = 1
→ R(N) = ½ N(N+1) + 1
Now let us examine Circles in the same way:
Again 0 circles gives just 1 region.
1 circle gives 2 regions.
Lets do up a table:
Now let's do our telescoping method again.
R(1) – R(0) = 1 R(2) – R(1) = 2 R(3) – R(2) = 4 R(4) – R(3) = 6 ….................... R(N) – R(N1) = 2N – 2 (except for R(1) – R(0))
Now adding them we eliminate all but R(N) and R(0)
R(N) – R(0) = + 1
Now let's do the same as last time to get
2 + 4 + 6 + 8 + …... + 2N – 2 2N2 + 2(N2)2.......+2  2N + 2N + ….......+2N
There are N1 terms as we started at R(2)
2S = (N1)2N
S= N(N1)
R(N)  R(0) = N(N1) + 1
R(0) = 1
→ R(N) = N(N1) + 2
Let us look at the problem of dividing a plane by both:
This is an interesting problem to investigate as it involves looking for patterns, we start off small and work our way up.
I have drawn the first 4 maps. We are looking for the maximum number of regions so I make sure the lines intersect each circle and do not cross at another intersection.
0 circles and 0 lines We have just 1 region (The plane itself)
1 Circle and 1 line
We have 4 regions in total.
2 Circles and 2 Lines
We have 14 regions in total.
3 circles and 3 lines
We have 31 regions in total.
4 circles and 4 lines
We have 55 regions in total (count them if you can;)
So in summary
So we have found our pattern, the next term is 7 more than the sum of the last term (except) the first term.
So we now know that R(5) will be 55 + 31 = 86
Let's come up with a recursive formula to get a general solution:
Each subsequent R(n) is a multiple of 7 added on to the previous term (+ 3 from the first case)
Therefore:
Here is a simple BASIC program to calculate R(n) relatively quickly:
Putting 20 into this gives 1391.
We want a general formula
Now let's do our telescoping method again.
R(1) – R(0) = 3 R(2) – R(1) = 10 R(3) – R(2) = 17 R(4) – R(3) = 24 ….................... R(N) – R(N1) = 7(N1)+3
Now adding them we eliminate all but R(N) and R(0)
R(N) – R(0) =
Now let's do the same as last time to get
3 + 10 + 17 + 24 + …...........+ 7(N1) + 3 7(N1)+3+.................................................+ 3  [7(N1)+3+3] + [7(N1)+3+3] +..............+[7(N1)+3+3]
2S= N(7(N1)+6)
S= ½ [N(7(N1)+6)]
R(N) – R(0) = ½ [N(7(N1)+6)]
R(0) = 1
→ R(N) = ½ [N(7(N1)+6)] + 1
Tidy this up to:
→ R(N) =
Putting 20 into this formula we get:
NOTES:
Interestingly enough this sequence is on the Online encyclopedia for integer sequences but (was not at the time) related to this problem
So from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jul 31 2009, we have another general formula for this recurrence:
putting n = 20 we have:
Also Note: It is possible to draw these maps with only 2 colours without the same colour meeting at a boundary (it is allowed meet at a point), I will leave that for you to prove... To get some background on proving 2 colouring of a map see:
http://mathforum.org/library/drmath/view/62500.html
