問題
以下が今回話題にあげる問題です。まだ解いてない方は先に解いてみることをお勧めします。
解説
本題の解説です。
はい、"解説"が今回記事にしようとしたきっかけです。
解説見ると以下のような内容が書いてあります。
実は、
(A_i + B_i) mod N
で分類することができます。
なんで？
というわけでこれを示してみる、というよりこの結果にいきつく思考を出してみます。
ですので厳密な話をするというより、1ペナ覚悟で提出するものを制作するという目的でやってみます。
「交わる」とは
サンプルを見ていただければなんとなくわかると思いますが、平行ではないということです。
つまり全ての組み合わせから互いに平行な直線を除けば求める解を得られることがわかります
互いに平行とは
直線同士が互いに平行になる条件とは
調べると以下のような内容が出てきます1
\displaylines
{2直線 y = m_1x+n_1, y = m_2x+n_2 が平行になる条件 \\
m_1 = m_2}
つまり直線の式の傾きを求めればいいんだなってわかります。
なら傾きを求めるには？こんどはこのページ2を見てみると
m =\frac{y_2-y_1}{x_2-x_1}
と出てきます。なら座標を出してみようと思ってここからさらに検索などをしていくと最終的に三角関数が出てきて発狂して死にます。これが円の怖いところですね。
ではどうするのか。幾何の問題が出てきたらやれと言われたことがあるかもしれないこと、そう図を描くのです。
図を描く
描かせました。水色の点を$i$番目、緑色の点が$j$番目の点となります($i<j$)
三角関数を避けるために図を描きましたが、傾きを求めるという点はかわりません。ではここからどのようにして傾きを求めるのか。
「傾き」という単語の意味を考えればわかります、そう角度です。
ここからどのようにして角度を求めるか。残念ながらここで多少の数学的センスが求められます、補助線を引くのです。
そうすると以下二つの角度がわかります。
\displaylines{
(水色の角度) = \frac{2\pi}{n} i\\
(オレンジ色の角度) =\frac{2\pi}{n} j
}
となります。そうすると先ほど補助線を引いた結果でてきた三角形の角度がわかります
\displaylines{
(オレンジ色の角度)-(水色の角度) = \frac{2\pi}{n} j - \frac{2\pi}{n} i\\
=\frac{2\pi}{n}(j-i)
}
説明のために図を変えます
補助線で作成した三角形にてx軸で分断した上の部分に着目してみます。
そうすると最終的に求めたい角度は以下のようにだせることがわかります。(最初にこれを想定するべきでした)
(求めたい角度) = (黄色の角度) + (ピンク色の角度)
円の性質を利用することで補助線を用いて描いた三角形が二等辺三角形であることを利用すれば導けます。
\displaylines{
(ピンク色の角度) = \frac{1}{2}(\pi-\frac{2\pi}{n}(j-i)) \\
=\frac{\pi}{2}-\frac{\pi}{n}(j-i)
}
次に黄色の角度を求めます。図を見れば90度から水色の角度を引いたものだとわかります。
\displaylines{
(黄色の角度) = \frac{\pi}{2} - (水色の角度) \\
=\frac{\pi}{2} - \frac{2\pi}{n} i
}
最後に求めたい角度を出してみます。
\displaylines{
(求めたい角度) = (黄色の角度) + (ピンク色の角度) \\
= (\frac{\pi}{2} - \frac{2\pi}{n} i) + (\frac{\pi}{2}-\frac{\pi}{n}(j-i)) \\
=\pi - \frac{i+j}{n}\pi
}
それで？
$n$も$π$も定数です。つまり角度は$i+j$という数値によってのみきまり、これが同じ場合は同じ傾き、つまりは平行であるということがわかります。
mod nはどこにいった？
ここで直線aと直線bの傾きを調べたいと思います。このときそれぞれの$i+j$を$\alpha, \beta$とします。一致はしませんが、$\beta = \alpha+ n$(つまり$\beta \equiv \alpha \mod n$)であった場合どうなるか。
先ほどだした角度に代入し確かめてみます。
\displaylines{
\alpha = i+j\\
とおく。このとき\\
\beta = \alpha+ n \\
= i+j+n\\
となる。ここで先ほどの傾きの式に代入して調べる \\
(直線aの傾きの角度) = \pi - \frac{i+j}{n}\pi \\
(直線bの傾きの角度) = \pi - \frac{i+j+n}{n}\pi \\
= \pi - (\frac{i+j}{n}\pi + \frac{n}{n}\pi) \\
= \pi - \frac{i+j}{n}\pi -\pi \\
= (直線aの傾きの角度) -\pi
}
つまり直線bの傾きは直線aを180度回しただけのものです。つまり平行です。
まとめ
解説通り、$(A_i + B_i) mod N$で分類することができました。
こう描いたら変になったんだけど
ごめんなさい、i,jの取り方によっては今のような解き方ができないかもしれません。がんばってください（投げやり）
おまえここ（数学的に）厳密じゃないぞ
とりあえずコードに書き起こせるきっかけを生み出すための思考をトレースしただけなので厳密性はあまり考えてません、ごめんなさい
おまえここ間違えてるぞ
コメントで指摘してくださると修正するかもしれません
グラフ描画のコード
Qiitaでプログラミングの話をしないのはまずいと思いますので記事内のグラフを描画したコードを以下に記します。（ありがとう、ChatGPT）
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Arc
import math
# 単位円のデータ
theta = np.linspace(0, 2 * np.pi, 300)
x_circle = np.cos(theta)
y_circle = np.sin(theta)
# 点i（第一象限）と点j（第四象限）の角度（単位：ラジアン）
theta_i = np.radians(30) # 第一象限：30度
theta_j = np.radians(-60) # 第四象限：-60度
# 点の座標
i = (np.cos(theta_i), np.sin(theta_i))
j = (np.cos(theta_j), np.sin(theta_j))
# x軸との交点を求める：線分 i->j に対して y=0 の t
t = -i[1] / (j[1] - i[1])
x_intersect = i[0] + t*(j[0] - i[0])
intersection = (x_intersect, 0)
# x軸とのなす角度（線分の傾きの絶対値から求める）
slope = (j[1] - i[1]) / (j[0] - i[0])
angle_rad = np.arctan(abs(slope))
angle_deg = np.degrees(angle_rad)
# 新たな点 y（座標 (0,1)）
y_point = (0, 1)
# 描画
fig, ax = plt.subplots()
ax.plot(x_circle, y_circle, label='Unit Circle') # 単位円
ax.plot([i[0], j[0]], [i[1], j[1]], 'r--', label='Line between i and j') # iとjを結ぶ線
ax.plot(*i, 'bo', label='Point i (Q1)') # 点i
ax.plot(*j, 'go', label='Point j (Q4)') # 点j
# 原点とi, j, yを結ぶ線分
ax.plot([0, i[0]], [0, i[1]], 'k--', label='Line from origin to i')
ax.plot([0, j[0]], [0, j[1]], 'k--', label='Line from origin to j')
# もともとの弧（x軸との交点付近の弧）
arc_radius = 0.2
arc = Arc(intersection, 2*arc_radius, 2*arc_radius, angle=0, theta1=0, theta2=angle_deg, color='purple')
ax.add_patch(arc)
# 原点を頂点とする角度の弧の描画
# ∠yoj: 頂点 o、点 y=(0,1)（角度 90°）と j=(cos(-60), sin(-60))（角度 -60°＝300°）の間の小さい角（150°）
arc_yoj = Arc((0,0), 0.4, 0.4, angle=0, theta1=-60, theta2=90, color='orange')
# Arc for ∠Oik at vertex i (between ray i→O and ray i→k)
vec_iO = (0 - i[0], 0 - i[1])
vec_ik = (intersection[0] - i[0], 0 - i[1])
angle_iO = math.degrees(math.atan2(vec_iO[1], vec_iO[0]))
angle_ik = math.degrees(math.atan2(vec_ik[1], vec_ik[0]))
start_angle = min(angle_iO, angle_ik)
end_angle = max(angle_iO, angle_ik)
arc_Oik = Arc(i, 0.4, 0.4, angle=0, theta1=start_angle, theta2=end_angle, color='magenta')
ax.add_patch(arc_Oik)
# Arc for ∠iOk at vertex O (between ray O→i and ray O→k)
vec_Oi = (i[0], i[1])
vec_Ok = (intersection[0], 0)
angle_Oi = math.degrees(math.atan2(vec_Oi[1], vec_Oi[0]))
angle_Ok = math.degrees(math.atan2(vec_Ok[1], vec_Ok[0]))
start_angle2 = min(angle_Ok, angle_Oi)
end_angle2 = max(angle_Ok, angle_Oi)
arc_iOk = Arc((0, 0), 0.5, 0.5, angle=0, theta1=start_angle2, theta2=end_angle2, color='yellow')
ax.add_patch(arc_iOk)
# ∠yoi: 頂点 o、点 y=(0,1)（90°）と i=(cos(30), sin(30))（30°）の間の角（60°）
arc_yoi = Arc((0,0), 0.6, 0.6, angle=0, theta1=30, theta2=90, color='cyan')
ax.add_patch(arc_yoi)
# 軸設定
ax.set_aspect('equal')
ax.grid(True)
ax.axhline(0, color='black', linewidth=0.5)
ax.axvline(0, color='black', linewidth=0.5)
ax.set_xlim(-1.5, 1.5)
ax.set_ylim(-1.5, 1.5)
ax.legend(loc='lower left')
plt.title("Unit Circle with Additional Arcs for ∠yoj and ∠yoi")
plt.show()
感想
めちゃくちゃ見ずらい記事になったなって気分