The star-shaped polygon (M, N) is a geometric shape which can be drawn by carrying out the following algorithm:

STEP 1: Construct the parent polygon with N sides.
STEP 2: Select any one of the vertices and label it 'visited'.
STEP 3: Draw a segment from the last vertex you 'visited' to the next one by jumping M vertices in an anti-clockwise direction. Label the new vertex you reach as 'visited'.
STEP 4: Repeat STEP 3 until the segment you draw joins up with a vertex you have already visited.

To start with, you can see different star-shaped polygons in the following window.

2.- Give N a fixed value (not very big) and click on M and hold. You should see something like a fast-moving film which, if you look at carefully, is actually the same sequence repeated over and over again, even though the value of M keeps changing.

The following window puts the algorithm described above into practice.

  Will it ever stop?

You will probably be able to answer this question yourself. As the number of vertices on the parent polygon is finite then we will reach the point where we draw a segment which joins up with a vertex we have already visited.

This way of reasoning is common in maths and is sometimes referred to as the 'Pigeon-hole Principle'. This principle states that ' if there are more pigeons than holes in a dovecote then there must be at least two pigeons in one of the pigeon holes'. Try to use this principle to explain why if 366 people attend the same meeting at least two of them will share the same birthday.

2. - As far as accuracy is concerned: At the end of the process will the final result always be a star-shaped polygon?

This question is more difficult to answer. However, to begin with you should see the need to ask yourself 'is it possible for the two numbers (N, M) to produce something other than a star-shaped polygon?' Let's look at a few problems that may arise:

1. If you select the pairs of numbers (2,8) and (3,15) in the window you will see that the result we get is not what we would normally call a 'star' as the sides should cross. What we get instead is a 'normal' polygon.
2. If you select the pairs of numbers (6,15) and (2,5) in the window we get the same star-shaped polygon but not all the vertices on the parent polygon are visited in the first example. This problem is not too serious, but we have tried to avoid it in our algorithm. In other words there will not be two different sets of numbers for the same star and we will choose the set that visits all the vertices of the parent polygon.
3. What is less likely to occur is to select a pair of numbers (M,N) which give us no polygon whatsoever. This would occur if the algorithm did not finish at the same vertex where it began. This problem seems very straight forward does not have an immediate solution.

There is a clear connection between the answers to the first two problems. The anomaly in the first example is fairly obvious. The pairs of numbers (2,8) and (3,15) illustrate this case where M, the number of vertices we jump, divided into N, the number of sides of the polygon gives us the number of 'visits' we make (N/M) before returning to the vertex we started with. The result is a regular (non star-shaped) polygon with this number of sides (N/M). We cannot form a star as by just going round the polygon once we can see that the lines do not cross each other at any point. Therefore, we must make sure that in our algorithm M cannot be divided exactly into N.

In the second example M does not divide exactly into N but the following pairs of values (6,15) and (2,5) or  (6,14) and (3,7) in the first window give us the exact same star. It is quite clear that (6,15) = (3·2,3·5) and that (6,14) = (2·3,2·7), i.e. that in both cases M and N have a common divisor. We therefore need to make sure that the numbers (M, N) do not have a common divisor, i.e. that the greatest common divisor is 1. We can simplify this to gcd (M,N)=1. When this happens we can say that numbers M and N are relatively prime. If we want to use two values (M,N) to find us a pair of numbers which are relatively prime and which produce the same star, we have to divide them by the greatest common divisor. You can review how to work this out by going to the gcd link. Can you give a mathematical explanation why all the vertices are 'visited' when gcd (M,N)=1? It is difficult to do, as we have already discovered by looking at the example, and does go beyond the main aim of this unit.

We still need to answer the last question we asked ourselves. When we put the algorithm into practice we know that at some point we are going to arrive at a vertex V, which we have already visited (think back to the pigeon-hole principle) and the algorithm will stop. We will have needed to go round the parent polygon more than once and we will get to this vertex for the first time after a set number of jumps, which we can call k, and a second time after a set number of jumps k' (k' is bigger than N to make sure that we go round the polygon more than once). It is clear that k<k'. This means that if we are at V and we jump k-k' times we end up at V again. However, this needs to be the case for each vertex that has been visited, and not just V, as the vertices are positioned symmetrically around the edge of the parent polygon. Therefore, we also need to apply that covered in step 2 to the vertex we start from.

STEP 2 Select any one of the vertices and label it 'visited'.

This also means that the first vertex we 'visit' is also the first one to be 'visited' twice as the others are all 'visited' after the first one.