N芒星の数学的側面

# はじめに

プログラムの講義で「N芒星の描画」をやりました。五芒星や七芒星はうまく描けますが、Nが偶数の時には工夫が必要で、特にN=6の時には *一筆書きの* 六芒星はうまく描けません。そのあたりを説明してみます。[「九九の一の位」の数学的側面](https://qiita.com/kaityo256/items/ab5e06f1352fdd333879)と本質は同じ問題です。

# コード

まず、N芒星を描画するコードを書いてみます。こんな感じです。

```py
from math import cos, sin, pi
from PIL import Image, ImageDraw
from IPython.display import display


def star(N, k):
    im = Image.new("L", (256, 256), 255)
    draw = ImageDraw.Draw(im)
    cx = 128
    cy = 128
    r = 96
    draw.ellipse((cx - r, cy - r, cx + r, cy + r))
    s = 2*pi/N
    for i in range(N):
        s1 = ((i*k) % N)*s - 0.5*pi
        s2 = s1 + s*k
        x1 = r*cos(s1)+cx
        y1 = r*sin(s1)+cy
        x2 = r*cos(s2)+cx
        y2 = r*sin(s2)+cy
        draw.line((x1, y1, x2, y2))
    display(im)
```

これは２つの数字、Nとkを指定すると、対応するN芒星を描画する関数です。五芒星を描くには(5,2)を指定します。

```py
star(5,2)
```

五芒星

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/78e310b2-63a4-95f8-0aa0-f50f359e94cd.png)

Nが奇数の時にはkとしてN//2を指定すれば同様なN芒星が描けます。

七芒星

```py
star(7,3)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/4dda806d-cca9-6c8f-ca5e-864cd9dced27.png)

九芒星

```py
star(9,4)
```


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/f8c44375-85c9-a8d3-4a1f-e57d41b1f0ad.png)

Nが偶数の場合も、kの値を工夫すればN芒星になります。

八芒星

```py
star(8,3)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/92ab8b07-43bf-2c2b-0473-57a46822931f.png)

十二芒星

```py
star(12,5)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/1d1a2290-654c-2dea-5cc8-381a3ea930c6.png)


しかし、N=6の場合にはうまくN芒星が描けません。例えばk=3とすると、

```py
star(6,3)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/a40b9489-6d15-9600-cee8-aabdc5988c3e.png)


と縦棒になってしまいます。k=2は三角形になります。

```py
star(6,2)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/98c0f750-2e2c-880e-cd5c-2c0229ebdc0a.png)

これはなぜでしょう、という問題です。

# 剰余類

まず、これは円をN等分し、その円周上の点を結ぶ問題になっています。`star(N, k)`は、0に次々とkを足していき、Nで割った余りに対応する数字を線で結ぶ関数です。これを(N, k)と呼びましょう。

例えば(5,2)なら、0に2を足していき、5で割った余りを追いかけます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/d734efed-e177-bd66-f16e-f257b15600cc.png)

途中で６と1、5と0を同一視しています。このように「Nで割った余りが同じなら、元の数字を同一視する」ことでできる構造を Nを法とする **剰余類** と言います。剰余類は同値類の一種です。

さて、Nを法とする剰余類は、N等分した円周上の点で表現するのが自然です。先程の数字の通りに線を結んでいくと、五芒星が完成します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/553bbfcf-5629-5e06-5fbd-1886d5c0eb1e.png)

0→2→4まで来て、次は4+2=6ですが、この円周上では6は1と同一視されるので次は1に行きます。

この円周上の数字を同値類の代表元と呼びます。

# 巡回群

もともと整数には加減算が定義されているため、「Nで割った余りの世界」である剰余類でも加減算ができます。しかし、整数は加算の逆元は減算ですが、剰余類は、加算だけで逆元を作ることができます。

例えば、5を法とする世界では、「3を足す」というのと「2を引く」は等価です。例えば、4に3を足すと7ですが、7を5で割った余りは2なので、「4 + 3 = 2 mod 5」となり、「3を足す」というのが「2を引く」のと同じ結果になることがわかります。したがって、剰余類の世界では加算だけで演算が閉じ、逆元も存在するので、加算が群を作ります。

特に今回は「毎回2を足す」というように、ただ一つだけの操作を考えます。このようにただ一つの要素から生成される群を **巡回群** と呼びます。(5, 2)で五芒星ができるのは、5を法とする世界で2を加算するという操作が作る巡回群の要素が、0から4まですべての数字を尽くすからです。

さて、Nを法とする剰余類で、kを足すという操作が作る巡回群(N, k)の要素が、0からN-1すべてを尽くすかどうかは、Nとkが互いに素であるかどうかで決まります。

先程うまくN芒星ができた(5,2)(7,3)(9,4)(8,3)(12,5)は、全て違いに素な数字の組でできていることがわかります。特にNが奇数の時には、N = 2k + 1とすれば、Nとkは必ず互いに素になるのでN芒星を作ることができます。

# N芒星の性質

さて、N芒星は、Nを法としてkを加えていく操作で表現できるので、それを(N, k)と表現するのでした。この性質を見てみましょう。

まず、(N, k)と(N, N-k)は等価です。ただし、「書き順」が逆になります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/873f111c-cb19-f871-7f24-5b511f86fe6d.png)

また、Nとkが互いに素でない場合には、「約分」ができます。たとえば(10,4)は(5,2)と等価です(コピペミスで図が(5,3)になってますが気にしないでください)。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/f8609bd9-f0a7-5451-2b09-ab6889e55508.png)

# 一筆書きの六芒星ができない理由

ここまでで、一筆書きの六芒星ができない理由はわかるかと思います。(N,k)がN芒星になるためにはNとkが互いに素でなくてはいけませんが、N=6の時、6未満で6と互いに素な整数は1と5しかありません。5は6を法とする世界では-1と等価ですから、要するに自明なものしかない、ということです。というわけで、円周上の６つの点全てをめぐる組み合わせは(6,1)と(6,5)しかなく、それが作るのは単なる六角形になります。

また、(6,2)と(6,4)は互いに等価で、「約分」すると(3,1)ですから、三角形になってしまいます。

(6,3)にいたっては「約分」で(2,1)になるので、平面図形ではなくただの線分になってしまいます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/e6b9f403-1323-3f6a-1334-dd86bee9098e.png)

# まとめ

円周をN等分して、k個ずつ進むことでN芒星を書くプログラムで遊んでみました。Nが奇数の時にはN=2k+1とすることでNとkが互いに素になり、N芒星になります。六芒星を一筆書きで作ることができないのは、6より小さい正の整数で6と互いに素なものが1,5という自明なものしかないからです。

この課題、プログラムが短いわりに絵も出るし数学的背景が面白いのでわりと気に入ってるんですが、どんなもんでしょう？