A circle is drawn and 17 distinct points are chosen on it.
Each pair of these points is connected by a chord (136 line segments in total).
The points are chosen in such a way that no more than two chords intersect at the same point.
These chords divide the interior of the circle into many regions.
How many regions are there?
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.
What a great question... At first I was convinced it was just $2^{n-1}$ , so when I got to 31, I was sure I had mis-counted... But, alas, no! :0) (+1)
The Moser's Problem is a classic example of "unproved" induction!
Do you know a "one-idea" approach to establish that the number of regions is equal to the number of lines + the number of intersections + 1?
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".
@Geoff Pilling Here's the nice way to see the bijection.
There is no guarantee that your lowest-point map (from regions to points of interest) is injective.
For instance, if $n = 4$ and one of the points lies at the bottom of the circle, then that point will be the lowest point of four different regions.
Log in to reply
K, should be fixed now. The tricky part was finding a simple bijection from the lowest point to the corresponding line.
Log in to reply
Yep, that seems to work. When I first started thinking about this problem, I tried a similar approach but ran into this complication. While I thought it should be possible to find a solution of this kind, but I found my approach easier.
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}$
Do you know how to establish that the number of regions is equal to the number of lines + the number of intersections + 1?
There is a very nice bijection, similar to the regions of n-lines in plane problem.
Log in to reply
I just started drawing lines, and I noticed that each time I started a line I had defined a new region, and any time I crossed another line I added a new region. (and we started with one region)
Problem Loading...
Note Loading...
Set Loading...
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!