A little while back, science punk Frank Swain posted a mathematical puzzle on his blog. The puzzle can be described simply — space n points equally around the unit circle, and draw all possible lines connecting those points. How many triangles are there in the resulting graph?

The first couple of cases, n = 3 and n = 4 are easy — the answers are 1 and 8. For n = 5 it requires a little more thought, but stand-up mathematician Matt Parker has a very clear explanation of why the answer is 35 on his website.

Mystic Rose

The six-sided mystic rose

After that, it gets progressively more difficult to count the triangles. The diagram for n = 6 is on the right. Try keeping track of all those triangles in your head (although CloudoidLtd has a very pretty, and easy to understand, solution for n = 6 and n = 7 on his blog.) The answers there are 110 and 287.

I was inspired by a comment on Frank’s blog to try a more traditionally combinatorial approach to solving the problem. The key observation is that each triangle is made up of exactly three chords. These chords can intersect at one of the points around the circle, or they might intersect somewhere inside the circle. We just have to classify the different ways that three chords can intersect to form a triangle, and then count up how many there are in each case.

A guide to choosing

The explanation will require that we understand how to calculate the number of ways of choosing a set of k objects from a larger set of n objects. We use the notation (n,k) as a shorthand for this. We pronounce it “n choose k“, and we definite it mathematically by

(n,k) = n! / k! (n-k)!

The exclamation mark is the factorial function, which means that we multiply together every number from n all the way down to 1, so that for example 4! = 4 x 3 x 2 x 1 = 24 (we also have the useful convention that 0! = 1). If you’ve not seen this before, it can be a fun exercise to try and work out why (n,k) has to take this form.

Counting the triangles

We’re trying to count the number of ways that three chords of the circle can intersect to form a triangle. Each chord involves two points around the circle, so there are only four cases to consider:

Triangle with 3 points

1. The chords form a triangle between three points. This is the simplest case to consider. Every set of three points around the edge of the circle contributes one triangle, so the number of triangles is simply the number of ways of choosing 3 objects from a set of n objects, which is (n,3).

Triangle with 4 points

2. The chords form a line connecting four points. There are (n,4) ways of choosing a set of four points, and for each set of four points there are four ways we can arrange the chords so that they form a triangle. So this contributes another 4 * (n,4) triangles.

3. Two of the chords share a point, and the third chord cuts across them. This involves five points in total. There are (n,5) ways of choosing 5 points, and for each set there are five ways to arrange the chords so that they form a triangle. This contributes another 5 * (n,5) triangles.

Triangle with 5 points

4. None of the chords share a point, so there are six points in total. To make a triangle we have to join opposite points, so there is only one way of arranging the chords so that a triangle is formed. This gives another (n,6) points.

With all of this counting done, we have a formula for the number of triangles formed by the mystic rose with n points, which we denote by T(n):

T(n) = (n,6) + 5 (n,5) + 4 (n,4) + (n,3).

So how does this formula stack up when we compare it to the results we already know? With suitable adjustments for when n < 6 (because (n,k) is meaningless when k > n) we get

T(3) = 1, T(4) = 8, T(5) = 35, T(6) = 111, T(7) = 287 and T(8) = 644.

This works for most of the cases, but the actual answers for n = 6 and n = 8 are 110 and 632. The formula overcounts by one triangle for the 6-sided rose, and it overcounts by 12 triangles for the 8-sided rose. What’s going on?

Overcounting, and why the problem is hard

We can see the problem by looking at the 6-sided rose at the beginning of the post. The three chords which cut the circle in half all meet at the center. They don’t form a triangle, but our formula treats them as if they do. This is why it overcounts by 1.

It’s interesting to note that if the points weren’t equally spaced around the circle, but instead were randomly spaced, then we wouldn’t have this problem. It’s unusual for three lines in a plane to all intersect at the same point — it requires some special structure, and in this case the special structure is given by demanding that all the points lie on the vertices of a regular polygon. Injecting some more randomness into the problem would actually make it easier. The problem would be one of pure combinatorics — that is, just a problem of counting. Because of the additional regularity, we have made it a problem of geometry. Not only do we have to think about how the points are connected by lines, we also have to worry about the exact locations of the points. This is why the mystic rose puzzle is hard!

Finding the intersections

Whenever we have three or more chords intersecting at a point inside the circle, our formula is going to overcount the number of triangles, so we need to correct for this somehow.

Intersections at the center of the circle are easy to deal with. When there are n points, and n is even, then there are n/2 chords which pass through the center of the circle. Each set of three chords contributes one false triangle, and there are (n/2,3) ways of choosing 3 chords from a set of n/2, so we can modify our formula to:

T(n) = (n,6) + 5 (n,5) + 4 (n,4) + (n,3) – a(n) (n/2,3)

where a(n) = 1 if n is even, and a(n) = 0 if n is odd. This formula now gives the correct result for n = 6, although it still fails for n = 8.

A number of interesting hypotheses spring to mind, which would simplify the problem if they were true:

  1. The intersections only occur at the center of the circle.
  2. The intersections all occur along lines joining two points at opposite sides of the circle.
  3. The intersections all occur along symmetry axes of the rose.
  4. Except at the center, only three chords ever intersect at one point.

Unfortunately, none of these is true. Hypothesis 1 can be seen to be untrue if you look at the 8-sided roses in the pictures above. Around the center of the rose there are 8 points where three chords intersect. These explain 8 of the overcounted triangles. The other 4 are from the intersection of four chords at the center — every set of three chords intersecting at the center gives a false triangle, and there are (4,3) = 4 ways of choosing a set of three chords from four.

To see why Hypotheses 2 and 4 are false, we have to look at the 12-sided rose. Using the mystic rose drawer at nrich you can draw mystic roses with up to 20 points. For the 12-sided rose pictured on the right, we see that there is an intersection of 4 chords which doesn’t occur along a line joining two points on opposite sides of the circle. Damn!

The 4-chord intersection

To see why Hypothesis 3 is false, we have to look at the 16-sided rose. Now the three-point intersection doesn’t occur on a symmetry axis (can you see it? It’s in the top left quadrant of the picture). This means that this intersection is repeated 32 times around the circle, rather than the 16 times that we’d see if the intersection was on a symmetry axis.

A 3-chord intersection for n = 16

One hypothesis that does seem to be true is this one:

5. When n is odd, there are no intersections of three or more chords.

This means that our formula should work for all odd n, and indeed for every n that I’ve checked, the formula holds. I still don’t have a proof, though!

With all of these hypotheses rejected, we have to come up with a criterion for the intersection of three or more chords of the circle, and a way of determining how many such intersections there are when there are n points spaced equally around the edge of the circle. This is to come in Part II of this blogpost.

About these ads