Circles

1 circle can split the plane into at most 2 regions.
2 circles can split the plane into at most 4 regions.
3 circles can split the plane into at most 8 regions.
4 circles can split the plane into at most ______ \text{\_\_\_\_\_\_} regions.

13 14 15 16

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

8 solutions

Jason Dyer Staff
Aug 30, 2017

First note we can't do any better: a set of circles will divide the plane into a maximal number of areas if every possible pair intersects and no three are concurrent.

If we look at adding the k th k^{\text{th}} circle to an existing arrangement, it intersects each of the existing k 1 k-1 circles in 2 points, resulting in 2 ( k 1 ) 2(k-1) intersections and dividing the new k th k^{\text{th}} circle into 2 ( k 1 ) 2(k-1) arcs. Each arc splits one of the existing regions into two, as shown below.

Now let's justify the general formula (mentioned but not proven in other solutions) using this. As noted here, the 3rd circle increases the count by 2 ( 3 1 ) = 2 ( 2 ) = 4 , 2(3-1) = 2(2) = 4, the 4th circle increases the count by 2 ( 4 1 ) = 2 × 3 = 6 , 2(4-1) = 2 \times 3 = 6, the 5th circle increases the count by 2 ( 5 1 ) = 2 ( 4 ) = 8 , 2(5-1) = 2(4) = 8, and so on. (The first circle is unique in that it makes 2 regions even though it has no intersections.)

For n n circles, this results in the summation

2 + 2 + 4 + 6 + 8 + + 2 ( n 1 ) = 2 + 2 ( 1 + 2 + 3 + 4 + + ( n 1 ) ) 2 + 2 + 4 + 6 + 8 + \ldots + 2(n-1) = 2 + 2(1 + 2 + 3 + 4 + \ldots + (n-1))

After applying the arithmetic sum formula, this simplifies to

2 + 2 n ( n 1 ) 2 = n 2 n + 2 2 + 2\frac{n(n-1)}{2} = n^2 - n + 2

How do we show that a circle intersecting all existing k 1 k-1 circles at 2 ( k 1 ) 2(k-1) distinct points exists?

Pranshu Gaba - 3 years, 9 months ago

Log in to reply

You're just wanting a constructive way of fulfilling the number of intersections; one way is to just put all the circles in a line and have them be of increasing radius, so that the rightmost circle just makes it inside the leftmost circle.

Jason Dyer Staff - 3 years, 9 months ago

An interesting consequence is that we cannot explain all situations of a family of 4 sets with Venn Diagrams.

Agnishom Chattopadhyay - 3 years, 8 months ago

This is the best explanation hands down. Thanks.

patent fox - 3 years, 9 months ago
Deva Craig
Aug 21, 2017

4 circles can split the plane into at most 14 \boxed{14} regions

How do you know that 15 (or higher) cannot be achieved?

Pi Han Goh - 3 years, 9 months ago

Log in to reply

There are lots of problems that are related to the sources outside, much like this one that relates to WM article .

This problem can be solved by proving that the number of divided regions is n 2 n + 2 n^2 - n + 2 , or observing the number of regions.

Michael Huang - 3 years, 9 months ago

Log in to reply

This problem can be solved by proving a harder problem that generalizes this problem. Well, OK then. So how would that be done? Edit: I see the page linked to doesn't answer that question, either. Anybody got a reference to the source of the proof of this formula?

Richard Desper - 3 years, 9 months ago

Log in to reply

@Richard Desper Each circle can only intersect any other circle at at most 2 points, thus a new circle in a plane in which 3 are already present can have at most 6 new intersections. which creates at most 6 new areas. 8 + 6 = 14

Jacob Huebner - 3 years, 9 months ago

Also can solve by 2^n-n

Hong Sheng Tan - 3 years, 9 months ago

Log in to reply

No, it will not work.

Munem Shahriar - 3 years, 9 months ago
Munem Shahriar
Aug 28, 2017

Relevant wiki: Arithmetic Progression Sum

Assume this follows alphabetical orders. Look at the first 3 pictures,

Circle 1: 2 regions A , B \rightarrow A, B

Circle 2: 4 regions A , B , C , D 2 \rightarrow A,B,\color{#3D99F6} \underbrace{C,D}_2

Circle 3: 8 regions A , B , C , D , E , F , G , H 4 \rightarrow A,B,C,D, \color{#D61F06} \underbrace{E, F, G, H}_4

So for circle 4 it will be 14 \boxed{14} regions A , B , C , D , E , F , G , H , I , J , K , L , M , N 6 \rightarrow A, B, C, D, E, F, G, H, \color{#20A900}\underbrace {I, J, K, L, M, N}_6

So following this pattern, circle 5 will be 22 regions? 14+8

Jack Thias - 3 years, 9 months ago

Log in to reply

Yes, for circle 5 it will be 22 regions.

Munem Shahriar - 3 years, 9 months ago

Log in to reply

i think circle 5 will 'have' or 5 circles will have.

Mohammad Khaza - 3 years, 9 months ago

Well, this does not say anything. Why should this pattern be followed?

Agnishom Chattopadhyay - 3 years, 8 months ago
Mohammad Khaza
Aug 27, 2017

the number of split regions will be= n 2 n + 2 n^2-n+2

so,for 4 circles the region numbers will be = 4 2 4 + 2 = 14 4^2-4+2=14

explanation:this can be solved in 3 ways....

number-1....look at the difference of this pattern------2............4.............8............14.....

................................................... difference------------------2-----------4------------6-----------........................[everytime the difference before+2]

number-2.....[2,4,8,14].....this pattern can be generalized as (a) 2 n 2 2^n-2 .....() or n 2 n + 2 n^2-n+2 .......[this will also give the same result]

number-3.....look at this set region.......1 circle=1 region,.....2 circles=3 regions,....... 3 circles=7 regions...[not adding the outer part ]

...................so, from that pattern it is easy to say that if 4 circles there will be =13 regions.and total regions in 4 circles will

be= 13 + 1 = 14 13+1=14 ...........[adding the U set or outer set]

You need to be able to prove that generalization. Where did n 2 n + 2 n^2 - n + 2 come from?

Zach Abueg - 3 years, 9 months ago

Log in to reply

oh! that is a pretty simple and easy pattern to guess.this can be solved in many ways.......

number-1....look at the difference of this pattern------2............4.............8............14.....

................................................... difference------------------2-----------4------------6-----------........................[everytime the difference before+2]

number-2.....[2,4,8,14].....this pattern can be generalized as (a).....( 2 n 2 2^n-2 ) or ( n 2 n + 2 n^2-n+2 ).......[this will also give the same result]

number-3.....look at this set region.......1 circle=1 region,.....2 circles=3 regions,....... 3 circles=7 regions...[not adding the outer part ]

...................so, from that pattern it is easy to say that if 4 circles there will be =13 regions.and total regions in 4 circles will

be= 13 + 1 = 14 13+1=14 ...........[adding the U set or outer set]

Mohammad Khaza - 3 years, 9 months ago

Log in to reply

Why n = 4 ? n=4?

Munem Shahriar - 3 years, 9 months ago

Log in to reply

@Munem Shahriar only 1 circle---n=1,......................this is going like that. if you look at the pattern you will lough how funny question this is.

Mohammad Khaza - 3 years, 9 months ago

Log in to reply

@Mohammad Khaza I do not understand.

Munem Shahriar - 3 years, 9 months ago

Log in to reply

@Munem Shahriar just look at number-1 (pattern)-----2...4...8.....14....you can generalize the pattern with .... n 2 n + 2 n^2-n+2 or 2 n 1 2^n-1 .

everything in this world has an abstract pattern which can be generalized by mathematics.for this picture of circles the pattern---2...4...8....14.

so, for 1st sequence,n=1 ; for 2nd sequence,n=2...............

Mohammad Khaza - 3 years, 9 months ago

Doesn't work for n = 0. Where if n = 0, there would be 1 region.

Sean Leizerovich - 3 years, 9 months ago

a(2) - a(1) = 2, a(3) - a(2) = 4, ... a(n)-a(n-1) = 2(n - 1) (n-1 circles will split a circle into at most n-1 regions)

so:
a(n) - a(1) = 2+4+...+2(n - 1) = 2(1+2+...+n-1) = n^2 - n
a(n) = n^2 - n + 2 (n>=1)

z c - 3 years, 9 months ago
Jet Sri
Aug 27, 2017

Gabor Revesz
Sep 2, 2017

We can solve this problem by first solving it for lines (instead of circles) and then using stereographic projection to extend it to circles:

Whenever in a plane we have parallel lines or more than 2 2 lines intersect at the same point, we can add new regions (without destroying any existing ones) by slightly perturbing the lines involved. So for maximizing the number of regions we assume that no 2 2 lines are parallel and no 3 3 of them meet at a point. Given n n such lines in plane P P , each pair of them will intersect exactly once, at a point unique to the pair, for a total of

V = n C 2 V={_nC_2}

points of intersection, and each line will be partitioned into n 2 n-2 bounded and 2 2 unbounded segments by its n 1 n-1 points of intersection with the other lines. That's a total of

E = n ( n 2 ) E =n{\cdot}(n-2)

bounded and 2 n 2n unbounded segments. Since each unbounded region borders on 2 2 unbounded segments and each unbounded segment iborders on 2 2 unbounded regions, there are

U = 2 n U=2n

unbounded regions. To find the number B B of bounded regions, let's temporarily remove all the unbounded segments leaving behind a finite planar graph with a total of F = B + 1 F=B+1 regions (including the 1 1 unbounded one). Using Euler's V E + F = 2 V-E+F=2 we can find that

B = F 1 B=F-1

= ( E V + 2 ) 1 =(E-V+2)-1

= E V + 1 =E-V+1 .

This solved the problem for n n lines. Now stereographically project P { } P{\cup}\{{\infty}\} to a sphere S S . Then S S will be partitioned by n n circles into B + U B+U regions with all n n circles intersecting at the north pole. We can perturb these n n circles away from the north pole without destroying any of the U U regions already there locally resulting in B + U B+U regions, just like we did with the lines. Globally this will have added B B new regions to the B + U B+U already present, for a total of 2 B + U 2B+U regions. Projecting S S back onto P P results in n n circles, partitioning P P into

2 B + U 2B+U

= 2 ( E V + 1 ) + 2 n =2(E-V+1)+2n

= 2 ( n ( n 2 ) n C 2 + 1 ) + 2 n =2(n{\cdot}(n-2)-{_nC_2}+1)+2n

= n 2 n + 2 =n^2-n+2

regions.

Syrous Marivani
Sep 1, 2017

So, there are 14 regions A thru N.

Aviel Avshalumov
Aug 28, 2017

Imagine the pattern in the number of regions without A since regions are the being added to the circles only. Number of total regions - A: 1 circle: 1 regions 2 circles: 3 regions (2 added to the 1st region)
3 circles: 7 regions (4 added to the previous 4 regions) If you notice the pattern you can see that to find the # of regions for 4 circles we need to add 6 to the previous 7 regions. 4 circles: 7 + 6 = 13 regions Since we just calculated the # of regions without A we must add that back in for the total #. Therefore, 4 circles can split the plane into at most 13 +1 = 14 total regions

No proof yet that 14 is correct. Just pictures with counting or guesses that 0,2,4 implies that the next number is 6, the other solution like it.

Arthur Nadas - 3 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...