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