A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. In problem I. 59. of the informatics section of our 2003 October issue, the task was to draw all possible -pointed regular star polygons. These are obtained by connecting every -th vertex of a regular -gon (), starting at one vertex (Figure 1). Only those solutions are accepted that do produce an -pointed star.
Figure 1 Definition [1]. A regular star polygon consists of a finite number of line segments in the plane where each endpoint is incident to two line segments and there exists an isometry that maps one line segment onto any other one while mapping the polygon into itself. The boundary of a regular polygon is also a figure of this kind but that is not called a regular star polygon. Diagonals of a regular polygon equidistant (with a non-zero distance) from the centre form a regular star polygon. Consider the regular star obtained by applying the second part of the definition to a regular pentagon (Figure 2a).
Figure 2a For this star pentagon it is true that there is an isometry for any pair of its edges: they can be mapped onto each other by either a rotation or reflection in a line (Figure 2b). The name pentagon is slightly misleading: the stars of Figures 2 clearly have ten sides.
Figure 2b What further properties do these figures have? The regular star -gon has sides, the sides being equal due to the symmetries; all other angles (out of its angles) are equal, let the common measure be , and the remaining angles (let them be ) are also equal. It is straightforward from the sum of the angles of a polygon that Let be the initial vertex of the appropriate regular polygon, let denote the -th vertex and let be the vertex next to (in a clockwise direction). In the triangle (Figure 3a), (since we are dealing with -neighbouring vertices of a regular -gon), thus | | (1) | In the triangle | | (2) | Hence , that is, , a sum independent of . The value of can also be calculated from (1) and (2):
Figure 3a Rotational symmetry implies that every other vertex of a star polygon lies on a circle. Let and denote these two concentric circles (Figure 3b).
Figure 3b It seems that every other angle of a star polygon is concave. Is that true? If the radius of the inner circle is increased (or decreased), the resulting figure will also obey the definition, i.e. it will also be a star polygon but its sides will no longer lie on the diagonals of a regular polygon. The motion of the ``inner'' vertices can be continued until there are no more concave angles and the circle is not yet reached (when it is reached, a regular -gon is formed). This can be done since | | According to the definition this should also be a star polygon but if we do not want it to be, like in the case of the regular polygon, we can require additionally that every other angle of a star polygon should be concave. There is an intermediate state in which and the star polygon then reduces to a regular -gon.
Figure 4a If the inner circle is rotated about the centre, rotational symmetry is preserved but the axial symmetry mapping adjacent sides onto each other is destroyed. Thus the resulting ``circular saw'' is not a regular star pentagon (Figure 4b).
Figure 4b Let us consider now the solutions of the informatics problem obtained by connecting the vertices of a regular -gon to their -th neighbours. That results in a closed polygon whose sides may intersect [1]. (There are solutions to the problem.) If then the same diagram can be obtained by connecting each vertex to its -th neighbour. For even, will not provide a solution either; the result is a single line segment, a diameter of the circumscribed circle. Thus we can assume that . Let us first consider the case of (that was the example discussed in the informatics problem). allows: . If , the vertices in the order of connection are | | (In the 6th step, it would not make sense to write 12 since the 12th vertex coincides with the first one.) We know 11 is prime, so the polygon closes up in the 11th step. The possible cases are shown in Figure 5.
Figure 5 A similar result is obtained for any prime number . Then the possible values of are (where stands for the greatest integer not greater than ). Since is odd, is not a whole number, so the number of solutions is . If then allows , as shown in Figure 6. In the case of the polygon returns to the starting point in the 5th step without the line segments intersecting each other. A regular pentagon is obtained. We can observe in general that if divides then a regular -gon is obtained, which is not accepted as a solution.
Figure 6 In the case of we get a regular five-pointed star which could be a solution but it follows from the wording of the problem that it does not belong here: For we should get ten-pointed stars. In general, if and have common factors, that is, if they are not relative primes, then an -pointed regular star is obtained (where stands for the greatest common divisor of and ), which is not accepted as a solution. In the case of we do get a ten-pointed star. In general, if and are relative primes () then all vertices can be traversed without returning to the starting point before the -th step. The sides of the polygon will intersect each other, and we get an -pointed star. Eventually, we only obtained one ``good'' solution for although if the informatics problem were defined as the connecting of diagonals equidistant from the centre, we would have three of them (Figure 7.)
Figure 7 Does the problem always have a solution if is not a prime? For , can only be 2, which results in a regular triangle, not a solution. If is least 3 there is a smaller number that is relatively prime to it, for example . However, we are only using values of that are smaller than one half of . For there is no solution since the only number less than 3, one half of 6, that is relatively prime to 6 is 1. Are there any other numbers like that? We will show that there are not. The next composite number is . A relative prime less than its half is 3. For , 2 is a solution (but so is 4), for , 3 is a solution. Consider now the following product: where is the -th prime number. , which is clearly greater than 5 (its largest factor), thus for all there exists such that . Otherwise all the first three primes would appear among the prime factors of which would mean . The generalization is obtained similarly: If is smaller than the product of the first primes then some element of the set is relatively prime to . Thus if then there exists such that . In the interval we have already checked the numbers less than 11. For larger numbers it follows from the above that there is a number less than that is relatively prime to since every prime element of the previous set is less than half of 11. The lower limit of the th interval is the -th prime number and its upper limit which grows much faster then the lower limit, is the product of the first primes. Thus the length of the intervals grows very fast. (E.g. for the interval is and for it is .) From the second step onwards, the upper limit is always multiplied by a prime greater than 2, so there exists an interval for any , containing both and . Thus there will always be a prime less than in the set of primes corresponding to the interval that is relatively prime to . Hence the informatics problem has at least one solution for every . The number of solutions in general is where denotes the number of relative primes to that are not greater than . (To see this, observe that and are relative primes precisely when and are. On the other hand, if or then no solution is obtained.) The estimations above imply that if . This result certainly does not mean that a six-pointed star does not exist since we know that well (Figure 8). It is indeed formed by diagonals of a regular hexagon equidistant from the centre. In addition, it is the only polygon of that kind. If we want to get all possible star polygons, the informatics problem should be modified. If the polygon returns to the starting point, a new one should be started from the second vertex, then another one from the third vertex and so on as long as there are ``free'' vertices.
Figure 8 Complicated as the above considerations may seem, a simple program can be written for finding all the numbers that are relatively prime to a given number and are smaller than its half. Then we can obtain our ``good'' stars.
Bibliography
[1] | Hajós, György: Introduction to Geometry, Tankönykiadó (Budapest, 1991). |
|