Plane division by Lines AND Circles (Problem, Analysis and Solution)


back to maths puzzle page

D. Kinsella


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:


Number of lines

Number of Regions

Offsett

0

1

“+”1

1

2

“+”2

2

4

“+”3

3

7

“+”4

4

11

“+”5

.

.

.

N

R(N)

“+”N+1


We can easily work out a recursive formula to work out R(N), the number of regions produced by N lines.


R(N) = R(N-1) + 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(N-1) = 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 + N-1 + …......+ 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.



2 circles gives 4 regions.



3 Circles gives 8 regions.



4 circles gives 14 regions.


Lets do up a table:


Number of Circles

Number of Regions

Offsett

0

1

“+”1

1

2

“+”2

2

4

“+”4

3

8

“+”6

4

14

“+”8

.

.

.

N

R(N)

“+”N+1


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(N-1) = 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

2N-2 + 2(N-2)-2.......+2

-------------------------------

2N + 2N + ….......+2N


There are N-1 terms as we started at R(2)


2S = (N-1)2N


S= N(N-1)


R(N) - R(0) = N(N-1) + 1


R(0) = 1


R(N) = N(N-1) + 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


Number of lines and Circles

Maximum number of regions R(n)

Offset

2nd offset

0

1

“+” 3

“+3”

1

4

“+” 10

“+7”

2

14

“+” 17

“+7”

3

31

“+” 24

“+7”

4

55

“+” 31

“+7”


So we have found our pattern, the next term is 7 more than the sum of the last term (except) the first term.


  1. So how many regions will 5 circles and 5 lines create?


So we now know that R(5) will be 55 + 31 = 86


5

86

“+” 38

“+7”


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:


CLS

INPUT "How many circles and lines do you want"; N

r = 1


FOR i = 1 TO N

r = r + 7 * (i - 1) + 3

NEXT i


PRINT r



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(N-1) = 7(N-1)+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(N-1) + 3

7(N-1)+3+.................................................+ 3

--------------------------------------------------------------

[7(N-1)+3+3] + [7(N-1)+3+3] +..............+[7(N-1)+3+3]


2S= N(7(N-1)+6)


S= ½ [N(7(N-1)+6)]


R(N) – R(0) = ½ [N(7(N-1)+6)]


R(0) = 1


R(N) = ½ [N(7(N-1)+6)] + 1


Tidy this up to:


R(N) =


Putting 20 into this formula we get:





NOTES:


Interestingly enough this sequence is on the On-line encyclopedia for integer sequences but (was not at the time) related to this problem

On-Line Encyclopedia of Integer Sequences


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