Thread: Chords between 'n' points around a circle - maximum number of regions?

"What is the maximal number of regions that can be obtained by joining n points around a circle by straight lines? The first few values of this sequence are 1,2,4,8,16,... Here's a hint: the next value is not 32."

Hope that nobody will take offence if I use this space as a journal of my thoughts on this problem:

- The next value in the sequence is 31, intriguingly.

- If there are distinct points around the circle, the number of chords is .

- Having seen that enumerating intersections was useful in a previous simpler but similar problem (see https://nrich.maths.org/discus/messa...tml?1248745070), I have been trying to enumerate the number of intersections that do *not* occur on the circumference of the circle. (Clearly, there are chords between adjacent points, which create regions: regions closest to the circumference, and one central region. I hope that if I can enumerate the number of intersections that occur within the circle, I can deduce how this affects the division of this central region.) If we label a point on the circle , and work our way around the circle in one direction only, we may label the subsequent points . I will use the and symbols to denote position with respect to this order, with defined to be the least member.

The chord linking the points and I will denote . Suppose that the chord intersects with the chord where within the circle; then must adhere to the following:

and ( or ).

But how to enumerate these internally intersecting chords? I suppose that the points and in the above intersecting chord must not be adjacent. There are of qualifying chords that may play the role of . I suppose that I could enumerate the number of such pairs of chords (and therefore the number of internal intersections), noting that the intersecting chord pair will be counted twice in the calculation, since it may play the role as either or the role of .

I'm not sure if any of the last paragraph will make much sense to anyone else, but I hope that it will to me in the morning, when I shall think about this some more...

Any thoughts, or hints much appreciated.

1,2,4,8,16,31 - OEIS Search Results

Classic problem, there are several ways to arrive at an answer.

Following your current line of reasoning, here's a hint for thinking about how many intersection points there are:
For every intersection point internally (assuming you don't have three lines intersecting at one point), how many chords are involved? And how is a chord related to the number of points on the circumference of a circle? From this, you should be able to figure out how many internal intersections there are.

One solution to the problem, once you've figured out how to find the number of internal intersections, (and then think about number of edges) is to use Euler's formula (V-E+F=1, I'll leave it up to you to figure out why Euler's characteristic is 1 in this case)

A nifty way to look for a formula for the sequence blindly (not considering the geometry) is to use the method of finite differences: write out the differences between each consecutive term, and then for each of those differences, write out the difference of each consecutive pair of differences, and so on. When you are left with differences of 1, then that will tell you the form of the formula (if the 3rd differences are all equal to 1, then the formula is a cubic, and if the 4th differences are all equal to 1, then the formula is a quartic, etc.) From there, you can, with a bit of algebra, solve for each of the coefficients of the polynomial.

And finally, another way to approach this problem is to think about the regions that the circle is divided into in terms of n-gons, where a 2-gon is formed by two adjacent points around the circumference of a circle. So, with n circumference points, you will have n 2-gons, some 3-gons (triangles), 4-gons (quadrilaterals), 5-gons, etc.). Then think about two different ways you can find the sum of the vertices of these polygons, and two different ways you can find the sum of the interior angles of all of these polygons. This will give you two equations, and if you've got them correct, you should see a way of combining the two to find the sum of the number of (2gons+3gons+4gons+...).

The formula for the maximum number of regions formed by chords connecting n points on a circle is


That's why the first n= 1, 2, 3, 4, 5 gives powers of 2 while n= 6 misses the last 1. n= 7 would be 2⁶- 1- 6= 64- 7= 57.