- #1
genericusrnme
- 619
- 2
So over the course of yesterday and the day before that I've spent a few hours thinking about these problems;
1. Given a circle, place n points arbitrarily* on the edge and connect every point to every other point with a straight line. How many intersections do you get?
2. Given the same situation described above, how many m-gons** are formed?
*I'm going to discount any configuration where three or more lines intersect at one point however
**I'm only counting m-gons that don't have any lines passing through them, so I'd count two triangles stuck together at the hypotenuse as two 3-gons rather than two 3-gons and a 4-gon etc.
Now the first problem I solved fairly easily (it looks a little messy, the LaTeX sticks out like a sore thumb)
.
Take n points on a circle and label them, starting from some arbitrary point 1,2...n in a clockwise fasion and let the lines [itex]L_{a,b}[/itex] be the lines from point labeled by a to the point labeled by b where a<b. Let the number of intersections of the [itex]\left(
\begin{array}{c}
n \\
2
\end{array}
\right)[/itex] lines be denoted by [itex]\Gamma[n][/itex]. *For a line [itex]L_{a,b}[/itex] to intersect a line [itex]L_{c,d}[/itex] the points a and b must be on opposite sides of [itex]L_{c,d}[/itex]. Let [itex]\mathcal{A}[/itex] be the set of labels of points on the circle and let us define the left set of the line [itex]L_{c,d}[/itex], [itex]\mathcal{L}\left[L_{c,d}\right][/itex] as the set [itex]\{n\in \mathbb{N} : c < n < d\}[/itex] and naturally the right set [itex]\mathcal{R}\left[L_{c,d}\right][/itex] as [itex]\mathcal{A}-\{c,d\}\cup \mathcal{L}\left[L_{c,d}\right][/itex].
Let [itex]\Gamma[n-1][/itex] be given. Suppose we add one more point with the label n, since the labeling started at an arbitrary point we can always let the added point be n. If we let [itex]\gamma[n][/itex] be the number of new intersections when all possible lines from n are added we must have [itex]\Gamma[n] = \Gamma[n-1] + \gamma [n][/itex] and so we shall have a recurrence relation.
Since we require, for an intersection, that there is at least one point on each side of the line there must be no intersections on the lines [itex]L_{n-1,n}[/itex] and [itex]L_{1,n}[/itex] since [itex]\mathcal{L}\left[L_{n-1,n}\right]=\emptyset[/itex] and [itex]\mathcal{R}\left[L_{1,n}\right]=\emptyset[/itex]. Next let is define the number of 'free points' as [itex]m = \left|\mathcal{L}\left[L_{a,b}\right]\cup \mathcal{R}\left[L_{a,b}\right]\right| = n -2[/itex] and since [itex]\mathcal{L}\left[L_{a,b}\right]\cap \mathcal{R}\left[L_{a,b}\right]=\emptyset[/itex] this implies [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right| + \left|\mathcal{R}\left[L_{a,b}\right]\right| = m[/itex] for any line. We also see that [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right|= b - a-1[/itex] from the definition.
To find [itex]\gamma[n][/itex] we take a point labeled by a and let [itex]l[a][/itex] be the number of lines from [itex]\mathcal{L}\left[L_{a,n}\right][/itex] to [itex]\mathcal{R}\left[L_{a,n}\right][/itex], each of which must then intersect [itex]L_{a,n}[/itex], so [itex]\gamma [n] = \sum _a l[a][/itex]. For each a [itex]l[a][/itex] has [itex]\left|\mathcal{L}\left[L_{a,n}\right]\|\mathcal{R}\left[L_{a,n}\right]\right| = (n-a-1)(a-1)[/itex] and so [itex]\gamma [n] = \sum _{a=1}^m (n-a-1)(a-1)=\sum _{a=1}^m a(m-a)[/itex].
Which gives the relation, using the fact that [itex]\Gamma[3]=0[/itex]
[itex] \Gamma [n]=\Gamma [n-1]+\sum _{a=1}^m a(m-a)[/itex]
[itex]= \Gamma [n-2]+ \sum _{a=1}^{m-1} a(m-1-a) + \sum _{a=1}^m a(m-a)=\text{...}[/itex]
[itex]= \sum _{p=0}^{n-4} \sum _{a=1}^{n-2-p} a(n-2-p-a)[/itex]
And after a little work
[itex]\Gamma[n] = -\frac{n}{4}+\frac{11 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex]
*I believe an application of the mean value theorem would guarantee an intersection here
.
It seems to me that [itex]\Gamma[n][/itex] should be correct for the boundary of any convex space (I'm not sure if this is the correct term, I mean the one where a straight line can be drawn from any point to any other point without leaving the space) subset of [itex]R^2[/itex] and (I'm guessing) by extention anything isomorphic to a convex subset of [itex]R^2[/itex]
The second one however is giving me a little trouble. I've played about a little with n≤10 points on a cirlce and I've managed to work out how to;
1. Count the sum of the internal angles which I got to be [itex]\alpha[n] = (n-2)\pi + 2 \pi \Gamma[n][/itex]
2. Count the total number of corners which I got as [itex]\mathcal{C}[n]=4\Gamma [n]+n(n-2)[/itex] which is just 4 corners for every intersection and around the edge each point has n spewing forth which gives n-2 conrners, n points = n(n-2) extra corners.
3. Find the number of polygons given n points which I got as [itex]\Sigma [n]=1-\frac{7 n}{4}+\frac{23 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex] which I got in virtually the same way I counted the total number of intersections, the outer two lines give 1 extra 3-gon and every other line gives the number of new intersections + 1 extra polygons
I also noted that the no. m-gons seems to be monotonic increasing but I have no idea how I could get started on proving that, I'm also conjecturing that as long as three or more lines don't intersect at one point the number of m-gons is invariant under moving the n points around the boundary again I'm not sure how to prove this, all I've got is that the total number of polygons is invariant.
But just with 3 conditions I can only solve for n=6 (since polygons only start appearing at n=3), so I need a better approach than just trying to find more 'conserved quantities'.
Any hints as to where I could go next?
I'm running a little low on ideas
(I apologise if I missed something, this is turning into an essay :shy:)
1. Given a circle, place n points arbitrarily* on the edge and connect every point to every other point with a straight line. How many intersections do you get?
2. Given the same situation described above, how many m-gons** are formed?
*I'm going to discount any configuration where three or more lines intersect at one point however
**I'm only counting m-gons that don't have any lines passing through them, so I'd count two triangles stuck together at the hypotenuse as two 3-gons rather than two 3-gons and a 4-gon etc.
Now the first problem I solved fairly easily (it looks a little messy, the LaTeX sticks out like a sore thumb)
.
Take n points on a circle and label them, starting from some arbitrary point 1,2...n in a clockwise fasion and let the lines [itex]L_{a,b}[/itex] be the lines from point labeled by a to the point labeled by b where a<b. Let the number of intersections of the [itex]\left(
\begin{array}{c}
n \\
2
\end{array}
\right)[/itex] lines be denoted by [itex]\Gamma[n][/itex]. *For a line [itex]L_{a,b}[/itex] to intersect a line [itex]L_{c,d}[/itex] the points a and b must be on opposite sides of [itex]L_{c,d}[/itex]. Let [itex]\mathcal{A}[/itex] be the set of labels of points on the circle and let us define the left set of the line [itex]L_{c,d}[/itex], [itex]\mathcal{L}\left[L_{c,d}\right][/itex] as the set [itex]\{n\in \mathbb{N} : c < n < d\}[/itex] and naturally the right set [itex]\mathcal{R}\left[L_{c,d}\right][/itex] as [itex]\mathcal{A}-\{c,d\}\cup \mathcal{L}\left[L_{c,d}\right][/itex].
Let [itex]\Gamma[n-1][/itex] be given. Suppose we add one more point with the label n, since the labeling started at an arbitrary point we can always let the added point be n. If we let [itex]\gamma[n][/itex] be the number of new intersections when all possible lines from n are added we must have [itex]\Gamma[n] = \Gamma[n-1] + \gamma [n][/itex] and so we shall have a recurrence relation.
Since we require, for an intersection, that there is at least one point on each side of the line there must be no intersections on the lines [itex]L_{n-1,n}[/itex] and [itex]L_{1,n}[/itex] since [itex]\mathcal{L}\left[L_{n-1,n}\right]=\emptyset[/itex] and [itex]\mathcal{R}\left[L_{1,n}\right]=\emptyset[/itex]. Next let is define the number of 'free points' as [itex]m = \left|\mathcal{L}\left[L_{a,b}\right]\cup \mathcal{R}\left[L_{a,b}\right]\right| = n -2[/itex] and since [itex]\mathcal{L}\left[L_{a,b}\right]\cap \mathcal{R}\left[L_{a,b}\right]=\emptyset[/itex] this implies [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right| + \left|\mathcal{R}\left[L_{a,b}\right]\right| = m[/itex] for any line. We also see that [itex]\left|\mathcal{L}\left[L_{a,b}\right]\right|= b - a-1[/itex] from the definition.
To find [itex]\gamma[n][/itex] we take a point labeled by a and let [itex]l[a][/itex] be the number of lines from [itex]\mathcal{L}\left[L_{a,n}\right][/itex] to [itex]\mathcal{R}\left[L_{a,n}\right][/itex], each of which must then intersect [itex]L_{a,n}[/itex], so [itex]\gamma [n] = \sum _a l[a][/itex]. For each a [itex]l[a][/itex] has [itex]\left|\mathcal{L}\left[L_{a,n}\right]\|\mathcal{R}\left[L_{a,n}\right]\right| = (n-a-1)(a-1)[/itex] and so [itex]\gamma [n] = \sum _{a=1}^m (n-a-1)(a-1)=\sum _{a=1}^m a(m-a)[/itex].
Which gives the relation, using the fact that [itex]\Gamma[3]=0[/itex]
[itex] \Gamma [n]=\Gamma [n-1]+\sum _{a=1}^m a(m-a)[/itex]
[itex]= \Gamma [n-2]+ \sum _{a=1}^{m-1} a(m-1-a) + \sum _{a=1}^m a(m-a)=\text{...}[/itex]
[itex]= \sum _{p=0}^{n-4} \sum _{a=1}^{n-2-p} a(n-2-p-a)[/itex]
And after a little work
[itex]\Gamma[n] = -\frac{n}{4}+\frac{11 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex]
*I believe an application of the mean value theorem would guarantee an intersection here
.
It seems to me that [itex]\Gamma[n][/itex] should be correct for the boundary of any convex space (I'm not sure if this is the correct term, I mean the one where a straight line can be drawn from any point to any other point without leaving the space) subset of [itex]R^2[/itex] and (I'm guessing) by extention anything isomorphic to a convex subset of [itex]R^2[/itex]
The second one however is giving me a little trouble. I've played about a little with n≤10 points on a cirlce and I've managed to work out how to;
1. Count the sum of the internal angles which I got to be [itex]\alpha[n] = (n-2)\pi + 2 \pi \Gamma[n][/itex]
2. Count the total number of corners which I got as [itex]\mathcal{C}[n]=4\Gamma [n]+n(n-2)[/itex] which is just 4 corners for every intersection and around the edge each point has n spewing forth which gives n-2 conrners, n points = n(n-2) extra corners.
3. Find the number of polygons given n points which I got as [itex]\Sigma [n]=1-\frac{7 n}{4}+\frac{23 n^2}{24}-\frac{n^3}{4}+\frac{n^4}{24}[/itex] which I got in virtually the same way I counted the total number of intersections, the outer two lines give 1 extra 3-gon and every other line gives the number of new intersections + 1 extra polygons
I also noted that the no. m-gons seems to be monotonic increasing but I have no idea how I could get started on proving that, I'm also conjecturing that as long as three or more lines don't intersect at one point the number of m-gons is invariant under moving the n points around the boundary again I'm not sure how to prove this, all I've got is that the total number of polygons is invariant.
But just with 3 conditions I can only solve for n=6 (since polygons only start appearing at n=3), so I need a better approach than just trying to find more 'conserved quantities'.
Any hints as to where I could go next?
I'm running a little low on ideas
(I apologise if I missed something, this is turning into an essay :shy:)