17-gon In A Circle

We solve the problem generally for $N$ points. It is obvious that if $N = 0$ , there is only one region. Let $C_{ab}$ stand for the chord drawn from point $a$ to point $b$ .

We build the situation by adding one point at a time. When adding point $n$ , we draw the chords $C_{pn}$ , with $1 \leq p < n$ . When ever a chord intersects an existing region, it splits that region in two. Thus the number of regions added is the number of intersections between the new chords and the old regions.

Suppose we are drawing chord $C_{pn}$ . Through how many regions does it pass? Each pair of regions is separated by an existing chord. Thus the number of new regions created by chord $C_{pn}$ is one, plus the number of intersections between $C_{pn}$ and existing chords $C_{ab}$ .

It is not difficult to see that chords $C_{pn}$ and chords $C_{ab}$ intersect precisely if $1 \leq a < p < b < n.$

Thus the number of regions is

• 1 for the initial circle,

• plus the number of chords $C_{pn}$ , with $1 \leq p < n \leq N$ ,

• plus the number of chord intersections $C_{pn} \times C_{ab}$ , with $1 \leq a < p < b < n \leq N$ .

Thus the total number of regions is $1 + \left(\begin{array}{c} N \\ 2 \end{array}\right) + \left(\begin{array}{c} N \\ 4 \end{array}\right).$ Substitute $N = 17$ and we find $1 + \left(\begin{array}{c} 17 \\ 2 \end{array}\right) + \left(\begin{array}{c} 17 \\ 4 \end{array}\right) = 1 + 136 + 2380 = \boxed{2517}.$

Note: for $N = 1, 2, 3, \dots$ the numbers of regions are $1, 2, 4, 8, 16, 31, 57, 99, \dots$ This is the unique fourth-degree polynomial defined by $f(n) = 2^{n-1}$ for $n = 1, \dots, 5$ . Remarkable!

I give a solution using Euler's formula.

The number of vertices v = number of chord intersections + number of points on circumference = $\binom{n}{4} + n$ .

The degree of each point on the circle is = (n-1) + 2 = n + 1

The degree of each intersection point = 4

Also note that the number of edges e = $\frac{degree \times number \: of \: vertices}{2}$

$\therefore e = \frac{n\times (n+1) + \binom{n}{4}\times 4}{2}$ .

Using Euler's Formula : $v - e + f = 2$ , where $f$ denotes the number of faces in the graph(i.e., one more than the number we are after).

$\therefore F= f -1 = 1 - (\binom{n}{4} + n) + (\frac{n\times (n+1) + \binom{n}{4}\times 4}{2})$

Hence $F = \frac{1}{24}(n^4-6n^3 + 23n^2-18n + 24 ) = \binom{n}{4} + \binom{n}{2} + 1$ .

Using this result for the given question with n = 17, it follows that F = 2517.

[This solution is slightly incomplete. It provides a bijection for counting the number of regions.]

Here's the "one-idea" that explains why the number of regions (when maxed out) is equal to " 1 + number of intersections + number of lines (between 2 points)".

Take any configuration. Arrange it so that none of the lines are parallel to the horizontal or vertical, and that none of the points are at the bottom of the circle. For each region, consider the "lowest point".

1. Show that this lowest point is uniquely determined (thanks to the arrangement).
2. Show that this lowest point is either an intersection point, the endpoint of a line or the bottom of the circle.
3. If the lowest point is the endpoint of a line, we have to associate it to a corresponding line. We do so in the following manner. Draw a tangent to the point. The tangent has an "upper ray" and a "lower ray". We sweep from the upper ray, through the circle, to the lower ray. Then, for each region whose lowest point is this point, the line that it will be associated to, will be the last line of the region that passes through the sweep.
   A) This line is uniquely determined. In particular, for regions whose perimeter includes the circumference, it will still map to a line.
   B) Each region maps to a unique line and vice versa
   C) The number of regions whose lowest point is that endpoint, will be equal to the number of points that are vertically above it.
   
   
   

I was playing around with this problem quite a bit before I finally realized that the number of regions is equal to the number of lines + the number of intersections + 1, or:

$N_{\text{regions}} = N_{\text{lines}} + N_{\text{intersections}} + 1$

$N_{\text{lines}} = \frac{n(n-1)}{2}$

$N_{\text{intersections}} = \frac{n}{4}\sum_{i=1}^{n-3}i(n-2-i)$

$N_{\text{regions}} = \frac{n(n-1)}{2} + \frac{n}{4}\sum_{i=1}^{n-3}i(n-2-i) + 1 = \frac{17(17-1)}{2} + \frac{17}{4}\sum_{i=1}^{17-3}i(17-2-i) + 1 = \boxed{2517}$

A006533