ピザの定理はピザを均等に分配できるのか、プログラムで確認してみよう

皆さんはピザの定理を知っていますか？ピザを均等な面積で切り分ける方法はいろいろとありますが、この定理を用いても均等にすることができます。個人的には面白い定理だと感じたのですが、本当に等しい面積なのか試してみたくなり、プログラムを書いて可視化と確認をしてみました。

# ピザの定理とは
Wikipediaに詳しく書いてありましたので引用します。

>初等幾何学におけるピザの定理（ピザのていり、英: pizza theorem）は、円板をある方法で切り分けると、2つの部分の面積を等しくすることができるという定理である。
>
>$p$を円板内部の任意の点とし、$n$を$8$以上の$4$の倍数とする。まず$p$を通る任意の直線に沿って円板を切り、直線を$p$を中心に$\frac{2π}{n}$ラジアンずつ回転させてはそれに沿って円板を切るという操作を計$\frac{n}{2}−1$回繰り返し、$\frac{n}{2}$本の直線で円板を$n$個の部分に切り分ける。そして時計回りまたは反時計回りに各部分に番号を順に振る。このとき、
>『奇数番目の部分の面積の和は、偶数番目の部分の面積の和に等しい(Upton 1968)。』
>
>「[ピザの定理](https://ja.wikipedia.org/wiki/%E3%83%94%E3%82%B6%E3%81%AE%E5%AE%9A%E7%90%86)」 (2022年12月21日 (水) 06:32 UTCの版 『ウィキペディア日本語版』)

https://ja.wikipedia.org/wiki/%E3%83%94%E3%82%B6%E3%81%AE%E5%AE%9A%E7%90%86

下記に概念図を示します。(※この図は概念図なので角度が正確ではありません)
![概念図.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/9a6bedad-ec88-b9f8-163b-84e11e343460.png)
この図は$n=8$の例になります。円の中に任意の点$p$を設定し、その点を中心に$45$度ずつ回転した線を$4$本引き、円を$8$個の領域に分割しました。この時緑と赤の部分の面積が等しくなるというのが、ピザの定理です。

# 可視化プログラムの作成
そこで次のアプローチでプログラムを作成しました。
* 何人で分けるか、何本の線を引くかを入力する　(線の本数を$M$本とする)
* XY平面上に単位円（ピザ）を描画する
* 任意の点$P$と点$Q$をクリックで入力し、その2点を通る円弧$L$を描画する
* 円弧$L$上の点$P$で等角度になるように直線を計$M$本描画する
* キャンバス上でランダムな座標を選び、円の内側なら切り分けるユーザごとに色分けした色でプロットし、円の外側なら黒でプロットする
* 円の内側にプロットした個数を色ごとに数えて、割合を算出する

以下に作成したプログラムを記載します。プログラムはPython3で実装しました。描画にはmatplotlibを使用します。


<details><summary><b>ソースコードを表示（折りたたみ）</b></summary><div>

```python:pizza_cut.py
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import math
import time

rng = np.random.default_rng()
cmap = plt.get_cmap("tab10") #10色用意

gx = 0.0
gy = 0.0
gNewClick = False

def onclick(event):
    global gx,gy,gNewClick
    gx = event.xdata
    gy = event.ydata
    gNewClick = True
    
def main():
    global gx,gy,gNewClick

    print("Number of people to divide")
    div_num = int(input())

    print("Number of cuts")
    cut_num = int(input())

    if (div_num < 2)or(cut_num<=1):
        print("Bad parameter settings")
        exit()

    if (2*cut_num)%div_num != 0:
        print("Bad parameter settings")
        exit()

    # 単位円を描画
    fig=plt.figure()
    ax=fig.add_subplot(111)
    c = patches.Circle(xy=(0, 0), radius=1, fc='w', ec='black')
    ax.add_patch(c)
    plt.axis('scaled')
    ax.set_aspect('equal')
    cid = fig.canvas.mpl_connect('button_press_event', onclick)

    # カットする中心点を入力
    while True:
        plt.pause(0.01)
        if gNewClick == True:
            gNewClick = False
            print("Center point X:",round(gx,5),"Y:",round(gy,5))
            x0, y0 = gx, gy
            plt.plot(x0,y0,marker='.', markersize=10, color="r")
            break

    # カットする基準の線を決める
    while True:
        plt.pause(0.01)
        if gNewClick == True:
            gNewClick = False
            print("passes point X:",round(gx,5),"Y:",round(gy,5))
            x1, y1 = gx, gy
            # 中心点と同じ座標の場合、再度取得する
            if (x1==x0) and (y1==y0):
                continue
            plt.plot(x1,y1,marker='.', markersize=10, color="b")
            break

    # カットする線を描画する
    a = [] #傾き用リスト
    b = [] #切片用リスト

    # plotした2点から１つ目の一次関数を作成
    a.append((y1-y0)/(x1-x0))
    b.append(((y0+y1)-a[0]*(x0+x1))/2)
    x=(np.arange(-1,2))
    y=(a[0]*x + b[0])
    plt.plot(x,y,color="k")

    # 残りの一次関数を作成
    for i in range(1,cut_num):
        theta = math.pi/cut_num*i
        xd = ((x1-x0)*math.cos(theta) - (y1-y0)*math.sin(theta))+x0
        yd = ((x1-x0)*math.sin(theta) + (y1-y0)*math.cos(theta))+y0
        a.append((yd-y0)/(xd-x0))
        b.append(((y0+yd)-a[i]*(x0+xd))/2)
        y=(a[i]*x + b[i])
        plt.plot(x,y,color="k")

    plt.pause(1.00) #plot前に一度描画する

    # 計算しやすいように一次関数を傾き順に並び替えておく
    newA = []
    newB = []
    npa = np.array(a)
    npa_sort_index = npa.argsort()
    for i in range(len(npa)):
        newA.append(a[npa_sort_index[i]])
        newB.append(b[npa_sort_index[i]])
    a = newA
    b = newB

    # 領域ごとの分配を決めておく
    dot_count = [0]*div_num
    region_map = [0]
    for i in range(1,cut_num+1):
        region_map.append(region_map[-1]+2**(i-1))
    for i in range(1,cut_num):
        region_map.append(region_map[-1]-2**(i-1))
    region_dict = {}
    for i in range(len(region_map)):
        region_dict[region_map[i]] = i%div_num

    # ランダムにプロットする
    start_time = time.time()
    for i in range(500000):
        curX = (rng.random()*2)-1
        curY = (rng.random()*2)-1

        if curX**2 + curY**2 <= 1:
            hit_cnt = 0
            for j in range(len(a)):
                if a[j]*curX+b[j] < curY:
                    hit_cnt += 2**j
            set_color = region_dict[hit_cnt]
            dot_count[set_color] += 1
            plt.plot(curX,curY,marker=',',markersize=1, color=cmap(set_color))
        else:
            plt.plot(curX,curY,marker=',',markersize=1, color="k")

        if i%1000 == 0:
            now = time.time()
            print(i//1000, round(now-start_time,2))
            #plt.pause(0.0001) # リアルタイム可視化する場合は、コメントアウトを外す

    # サマリ出力
    end_time = time.time()
    print("--------------------------------------")
    print("div:", div_num, "cut:", cut_num)
    print("X:",x0," Y:",y0)
    print("time", round(end_time-start_time, 5), "[s]")
    dot_sum = sum(dot_count)
    for i in range(len(dot_count)):
        print("color:",i+1,"count:",dot_count[i], round((dot_count[i]/dot_sum)*100, 5),"%")
    print("--------------------------------------")

    plt.show()

if __name__ == "__main__":
    main()

```

</div></details>

ちょっとだけプログラムを解説すると、座標の取得のためにクリックのコールバックイベントを登録しています。プロット数は$500000$個としました。この辺りは時間と精度を見ながら設定しています。

なお時間はかかりますが、リアルタイムにプロットの様子を可視化したい場合には、下記のコメントアウトを外してください。

```python
#plt.pause(0.0001)
```

リアルタイムの可視化の様子は次の通りです。(2人で4本の線で分けた場合)
![Figure-1-2024-06-19-22-32-07.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/41c4e9ac-15a3-6d62-20d5-a79397e00cfd.gif)

時間が進むにつれて青色とオレンジ色でピザ領域のプロットが進んでいくことがわかります。

:::note warn
映像ではマウスカーソルの位置との座標位置がずれているように見えますが、実際にはクリックした位置に赤点(点$p$)と青点(点$Q$)が描画されています。

またこの動画では変化が見やすいように、円内のプロットの形状とサイズを変更をスクリプトに加えています。
:::




# 結果の確認
それでは、可視化した結果を確認していきましょう。本当にピザの定理で分割した場合には、均等になっているのでしょうか。

### 2人に対して、4回のカットで分ける
まずは本記事の最初で、例として取り上げたパターンを確認してみましょう。

図のように中心やや左上に点$P$を、右下に点$Q$をそれぞれクリックにて設定しました。
![2-4_0_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/0ee742bb-b3fe-2d5e-79c2-93b746fa8462.png)

プロット後の画像は以下の通りです。
![2-4_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/b046033f-08ea-76c1-17b5-d01dbe9d1d48.png)
青色とオレンジ色に分けることができました。ところどころ白い点が見えますが、おおむね全体的にプロットができているようです。2色の面積は同じくらいに見えます。

次に出力されたサマリを確認します。
```
--------------------------------------
div: 2 cut: 4
X: -0.2321428571428572  Y: 0.020238095238095388
time 265.80061 [s]
color: 1 count: 196963 50.11768 %
color: 2 count: 196038 49.88232 %
--------------------------------------
```
divは分割する人数。cutはカットする回数です。XとYはそれぞれクリックした座標に対応しています。timeはプロットに要した時間です。

一人目(青色の領域)が196963プロットで$50.11768$[%]、二人目(オレンジ色の領域)が196038プロットで$49.88232$%となり、0.1%ほど誤差があるものの、等しいことを確認することができました。

点$P$と点$Q$の位置を変えてもう一度確認してみます。
![2-4_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/0b21842b-98a9-54f1-dd75-47a0b74909a1.png)
```
--------------------------------------
div: 2 cut: 4
X: -0.4464285714285714  Y: -0.5869047619047618
time 252.05639 [s]
color: 1 count: 196047 49.91649 %
color: 2 count: 196703 50.08351 %
--------------------------------------
```
今度は左下に点$P$を取ってみましたが、おおむね等しいことが確認できました。

### 2人に対して、8回のカットで分ける
続いて、カットの回数を増やし、8回行った場合を確認します。

![2-8_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/01b7fad9-0d5b-9990-1c91-967be9d3f830.png)

```
--------------------------------------
div: 2 cut: 8
X: -0.42261904761904767  Y: 0.4071428571428575
time 224.95408 [s]
color: 1 count: 196364 50.00458 %
color: 2 count: 196328 49.99542 %
--------------------------------------
```
カットの回数を増やした効果なのか、小数点以下2桁の精度で半分に分けることができました。

### 3人に対して、9回のカットで分ける
調べたところピザの定理は、2人に分けるだけでなく$N$人で分ける場合に、$N^2$の倍数で等角度にカットすると均等に分けることが可能とのことでした。証明は省略しますが、プロットで確認してみます。

![3-9_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/a0428c39-0187-eedd-0ccb-d6c45516d5f2.png)

```
--------------------------------------
div: 3 cut: 9
X: -0.6130952380952381  Y: 0.5142857142857147
time 208.92948 [s]
color: 1 count: 131019 33.33868 %
color: 2 count: 131220 33.38982 %
color: 3 count: 130755 33.2715 %
--------------------------------------
```
どの領域も33.3%に近く、3等分できているようです。

### 5人に対して、25回のカットで分ける

![5-25_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/afb23cd2-8949-2556-48fc-e21208d8e0b2.png)

```
--------------------------------------
div: 5 cut: 25
X: 0.4464285714285716  Y: -0.5988095238095237
time 221.15795 [s]
color: 1 count: 78494 19.96769 %
color: 2 count: 78749 20.03256 %
color: 3 count: 79081 20.11702 %
color: 4 count: 78552 19.98245 %
color: 5 count: 78229 19.90028 %
--------------------------------------
```

これも問題なく分けられているようです。ただ、もっとプロットの個数を多くしてもよいかもしれません。

## ピザの定理に当てはまらないパターン
つぎにピザの定理に当てはまらないパターンを確認してみます。

### 2人に対して、3回のカットで分ける
人数$N$に対して$N^2$回のカットでない場合、例えばカット数が少ない場合にはどのようになるのでしょうか。

![2-3_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/17b73ea4-913f-d5af-5fdf-91f4f2fc828d.png)

```
--------------------------------------
div: 2 cut: 3
X: -0.9583333333333336  Y: 0.014285714285714457
time 217.66594 [s]
color: 1 count: 162380 41.33016 %
color: 2 count: 230505 58.66984 %
--------------------------------------
```

オレンジの領域が広く、等分できていないことがわかります。なお点$P$をかなり円周近くに設定したのは、点$P$が円の中心付近にあると面積にあまり差がでないためです。もちろん完全に中央に点$P$を設定すれば、等分は可能です。


### 点Pをピザの外に設定し、3人に対して、9回のカットで分ける
つづいて点$P$が円の中にない場合をプロットしてみます。

![3-9_out_circle.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/693067/0f08416d-df93-854f-6787-ceed115aaa39.png)

図を見ただけではよくわかりません。サマリを確認します。

```
--------------------------------------
div: 3 cut: 9
X: -0.5654761904761905  Y: 0.9785714285714289
time 215.40883 [s]
color: 1 count: 139119 35.40284 %
color: 2 count: 130563 33.22552 %
color: 3 count: 123278 31.37164 %
--------------------------------------
```

円の外に点$P$を設定すると、確かに等分できていないようです。しかし点$P$が円周からあまり離れていないのもあり、3等分の33.3%に対して±2%程度の差になりました。円から離れれば離れるほど、面積の差は大きくなりそうです。

よくよく考えたら、点$P$がピザの外にあるので、9回カットできてなかったですね。

# 最後に
確かにピザの定理を用いれば、中心でカットしなくても同じ面積でピザを分けることができそうです。とは言っても「3人で分けたい場合にどうやって等角度に9回切るのか」という問題もあり、せいぜい4回切る程度が現実的でしょうか。

X(旧twitter)で拝見しましたが、この方は上手に切れていますね！！！すごい！！！

https://x.com/yokan0818/status/1799644620135243809

ここまで読んでくださって、ありがとうございました。

### 宣伝
最近考えた、算数の問題です。

https://qiita.com/osamuraislice/items/fc82e18bb5765bea7b48