有限体の勉強 〜麻雀大会組合せ問題への応用〜 [数学]
有限体について書かれたサイトをいくつか読んでいると、「麻雀大会組合せ問題」とでもいうべき問題に有限体 $F_4$ を使って解を与える方法がよく紹介されています（例えばこのサイトなど）。
僕はこれらの説明をパッと読んで、なんでこれでうまくいくのかがなかなか良くわかりませんでした。今日になってようやく理解できた気になりましたので、僕（サル）にもわかる書き方でうまくいく原理を紹介します。
「麻雀大会組合せ問題」とは次の問題です。
麻雀は一つの卓を$4$人で囲んで行うゲームですから、あるメンバーから見ると$1$ゲーム（「半荘（ハンチャン）」と言います）あたり$3$人と卓を囲むので、自分以外の$15$人全員とちょうど$1$回ずつ卓を囲むには半荘$5$回が必要なわけです。全メンバーがそのような卓の囲み方になるような計画ができるかという問題です。卓が$4$つあれば半荘$4$回が同時並行できるので、それも最大に活用して$16$名が無駄な待ち時間なく進むようにせよとの要求もあります。可能なのでしょうか。
この問題を解くのに、位数$4$の有限体 $F_4$ が使えるというのが今回の話です。
実は今回の話では「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使いません。体の構造がどうなっているかを考える必要はないのです。そこで $F_4$ の$4$個の元を、
\[ F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \} \]
とおきます。$e_1 \sim e_4$ のどれかが$0$だったり$1$だったりしますが、それは気にしなくても構いません。
まず、$F_4$ の元 $x,y$ の$2$つ組 $(x,y)$ を要素にもつ集合 $F_4^2$ を考えます。これを「$F_4$ 上の $xy-$平面」略して「$F_4$ 平面」と呼びます。
この集合の要素数は$16$で、これらを「$F_4$ 平面上の点」と呼びます。そして各点をそれぞれ麻雀大会のメンバー$16$人に割り当てます。
次に、$x,y$ を $F_4$ 上を動く変数とし、$a,b,c$ を $F_4$ 上の定数（パラメータ）として、次の$2$種類の式を考えます。
\begin{eqnarray*}
(A) \quad y &=& ax+b \\
(B) \quad x &=& c
\end{eqnarray*}
これらはどちらも $x,y$ に関する$1$次式ですので、「$F_4$ 平面上の直線」と呼びます。$(A)$ の形の直線はパラメータ $a,b$ の組合せで$16$通りあり、$(B)$ の形の直線はパラメータ $c$ の個数の$4$通りあり、合計$20$通りの直線があります。
ここで僕は、$F_4$ 平面のイメージとして $4 \times 4$ の格子状の点の並びをイメージしてしまったので、その上に直線がどのように引けるのかで困惑してしまいました。名前につられて幾何的な平面や直線をイメージするのはこの場合には逆効果です。以下の議論は純粋に代数的に考えることが肝要です。
$F_4$ 平面上の点と直線の関係には、普通のユークリッド幾何と同じ、次の性質が成り立ちます。
これらは $F_4$ が体であることから、次に示すように中学校の数学でやったのと全く同様のやり方で証明できます。
まず①を証明します。異なる$2$点を $(x_1,y_1), (x_2,y_2)$ とします。$x_1=x_2$ と $y_1=y_2$ は同時には成立しません。
$x_1 \neq x_2$ の場合を考えます。もしこれらを同時に通る直線があれば、それは $(B)$ の形ではありえませんので $(A)$ の形になり、
\begin{eqnarray*}
y_1 &=& ax_1+b \\
y_2 &=& ax_2+b
\end{eqnarray*}
が同時に成り立つはずです。上の式から下の式を引くと、
\[ y_1-y_2 = a(x_1-x_2) \]
となるので、$x_1-x_2 \neq 0$ と $F_4$ が体であることより、
\[ a = \frac{y_1-y_2}{x_1-x_2} \]
と $a$ が定まり、これを使って
\[ b = \frac{-x_1(y_1-y_2)}{x_1-x_2} + y_1 = \frac{x_1y_2-x_2y_1}{x_1-x_2} \]
と $b$ も定まり、従って直線が$1$つに定まります。この直線が実際に$2$点 $(x_1,y_1), (x_2,y_2)$ を通ることも確認できますので、$x_1 \neq x_2$ の場合に①が示されました。
$x_1=x_2, \ y_1 \neq y_2$ の場合は、$c=x_1=x_2$ としたときの $(B)$ の形が唯一の$2$点を通る直線になります。以上で①が証明されました。
次に②を証明します。ここでいう平行する異なる$2$直線とは、$a$ が同じで $b$ が異なる $(A)$ の形の$2$直線、または $c$ が異なる $(B)$ の形の$2$直線のことをいいます。
前者の場合、$b_1 \neq b_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
y &=& ax+b_1 \\
y &=& ax+b_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
y_0 &=& ax_0+b_1 \\
y_0 &=& ax_0+b_2
\end{eqnarray*}
より $b_1=b_2$ が導かれるので、矛盾を生じます。
後者の場合、$c_1 \neq c_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
x &=& c_1 \\
x &=& c_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
x_0 &=& c_1 \\
x_0 &=& c_2
\end{eqnarray*}
より $c_1=c_2$ が導かれるので、やはり矛盾を生じます。以上で②が証明されました。
さて、$F_4$ 平面上の直線についてはさらに次の性質があります。
これを示すために、$F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \}$ としたことを思い出しましょう。$(A)$ の形の直線 $y = ax+b$ については、
\[ (e_1, ae_1+b), \ (e_2, ae_2+b), \ (e_3, ae_3+b), \ (e_4, ae_4+b) \tag{1} \]
の$4$個の点を通り、それ以外は通りようがありません。また $(B)$ の形の直線 $x = c$ については、
\[ (c,e_1), \ (c,e_2), \ (c,e_3), \ (c,e_4) \tag{2} \]
の$4$個の点を通り、それ以外は通りようがありません。これで③が成り立つことがわかります。
直線に関する①②③の性質を使うと、麻雀大会組合せ問題が次のように解決されます。
まず、$a=e_1$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考え、これらの直線をそれぞれ雀卓に見立てます。性質③より各直線はちょうど$4$点を通り、それらは$(1)$を具体的に（ $F_4$ において）計算することによって特定できます。特定した各点にはそれぞれメンバーが割り当てられていますので、$4$台の雀卓にそれぞれ$4$人ずつのメンバーが割り当てられます。また、これら$4$本の直線は平行していますので、性質②より同じメンバーが$2$台以上の卓に割り当てられることはありません。従って、これで$16$人のメンバー全員が$4$卓を使って同時に半荘をプレイできることになります。
全卓が半荘$1$回終了したら、次に $a=e_2$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考えて同様に雀卓にメンバーを割り当てて半荘をプレイします。これが終わればまた $a=e_3, a=e_4$ として同様に続けます。最後に $c=e_1,e_2,e_3,e_4$ とした $(B)$ の形の$4$本の直線について$(2)$を用いて雀卓にメンバーを割り当てて半荘をプレイします。以上で同時に$4$卓ずつ$5$回、全部で$20$回の半荘がプレイされます。
そして、性質①によって、異なる$2$人のメンバーはちょうど$1$回だけ同じ卓に割り当てられます。
これで問題の要件を満足する麻雀大会の組合せを計画することができました。
この問題の解法をよく見ると、初めにことわったとおり、「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使っていないことがわかると思います。ということは、例えば位数$8$の有限体 $F_8$ を使って、
「$64$人の選手が、$8$レーンあるプールを使って水泳大会を行う場合の、各々の選手が自分以外の全ての選手とちょうど$1$回だけ同時に泳ぐような組合せ」
を計画することも、麻雀大会と全く同じ方法で可能なわけです（この場合各選手は全部で$9$回泳ぐことになります。かなりしんどい。）。さらに一般に、$q$が素数のべきであれば位数$q$の有限体 $F_q$ が存在しますので、$q^2$ 人のメンバーが $q$ 人ずつ組になって行う何らかの大会（人狼ゲームでも何でも可）の組合せが $F_q$ を使って上記の方法で計画できることになります。
（前記事）
僕はこれらの説明をパッと読んで、なんでこれでうまくいくのかがなかなか良くわかりませんでした。今日になってようやく理解できた気になりましたので、僕（サル）にもわかる書き方でうまくいく原理を紹介します。
「麻雀大会組合せ問題」とは次の問題です。
【問題】$16$人のメンバーで$4$卓を使用して麻雀大会を行う。$4$卓全てを同時に無駄なく使用し、しかも全てのメンバーが自分以外の$15$人と各々ちょうど$1$回ずつ卓を囲むような組合せを計画せよ。
麻雀は一つの卓を$4$人で囲んで行うゲームですから、あるメンバーから見ると$1$ゲーム（「半荘（ハンチャン）」と言います）あたり$3$人と卓を囲むので、自分以外の$15$人全員とちょうど$1$回ずつ卓を囲むには半荘$5$回が必要なわけです。全メンバーがそのような卓の囲み方になるような計画ができるかという問題です。卓が$4$つあれば半荘$4$回が同時並行できるので、それも最大に活用して$16$名が無駄な待ち時間なく進むようにせよとの要求もあります。可能なのでしょうか。
この問題を解くのに、位数$4$の有限体 $F_4$ が使えるというのが今回の話です。
実は今回の話では「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使いません。体の構造がどうなっているかを考える必要はないのです。そこで $F_4$ の$4$個の元を、
\[ F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \} \]
とおきます。$e_1 \sim e_4$ のどれかが$0$だったり$1$だったりしますが、それは気にしなくても構いません。
まず、$F_4$ の元 $x,y$ の$2$つ組 $(x,y)$ を要素にもつ集合 $F_4^2$ を考えます。これを「$F_4$ 上の $xy-$平面」略して「$F_4$ 平面」と呼びます。
この集合の要素数は$16$で、これらを「$F_4$ 平面上の点」と呼びます。そして各点をそれぞれ麻雀大会のメンバー$16$人に割り当てます。
次に、$x,y$ を $F_4$ 上を動く変数とし、$a,b,c$ を $F_4$ 上の定数（パラメータ）として、次の$2$種類の式を考えます。
\begin{eqnarray*}
(A) \quad y &=& ax+b \\
(B) \quad x &=& c
\end{eqnarray*}
これらはどちらも $x,y$ に関する$1$次式ですので、「$F_4$ 平面上の直線」と呼びます。$(A)$ の形の直線はパラメータ $a,b$ の組合せで$16$通りあり、$(B)$ の形の直線はパラメータ $c$ の個数の$4$通りあり、合計$20$通りの直線があります。
ここで僕は、$F_4$ 平面のイメージとして $4 \times 4$ の格子状の点の並びをイメージしてしまったので、その上に直線がどのように引けるのかで困惑してしまいました。名前につられて幾何的な平面や直線をイメージするのはこの場合には逆効果です。以下の議論は純粋に代数的に考えることが肝要です。
$F_4$ 平面上の点と直線の関係には、普通のユークリッド幾何と同じ、次の性質が成り立ちます。
① 異なる$2$点を通る直線は$1$本だけ存在する
② 平行する異なる$2$直線は点を共有しない
② 平行する異なる$2$直線は点を共有しない
これらは $F_4$ が体であることから、次に示すように中学校の数学でやったのと全く同様のやり方で証明できます。
まず①を証明します。異なる$2$点を $(x_1,y_1), (x_2,y_2)$ とします。$x_1=x_2$ と $y_1=y_2$ は同時には成立しません。
$x_1 \neq x_2$ の場合を考えます。もしこれらを同時に通る直線があれば、それは $(B)$ の形ではありえませんので $(A)$ の形になり、
\begin{eqnarray*}
y_1 &=& ax_1+b \\
y_2 &=& ax_2+b
\end{eqnarray*}
が同時に成り立つはずです。上の式から下の式を引くと、
\[ y_1-y_2 = a(x_1-x_2) \]
となるので、$x_1-x_2 \neq 0$ と $F_4$ が体であることより、
\[ a = \frac{y_1-y_2}{x_1-x_2} \]
と $a$ が定まり、これを使って
\[ b = \frac{-x_1(y_1-y_2)}{x_1-x_2} + y_1 = \frac{x_1y_2-x_2y_1}{x_1-x_2} \]
と $b$ も定まり、従って直線が$1$つに定まります。この直線が実際に$2$点 $(x_1,y_1), (x_2,y_2)$ を通ることも確認できますので、$x_1 \neq x_2$ の場合に①が示されました。
$x_1=x_2, \ y_1 \neq y_2$ の場合は、$c=x_1=x_2$ としたときの $(B)$ の形が唯一の$2$点を通る直線になります。以上で①が証明されました。
次に②を証明します。ここでいう平行する異なる$2$直線とは、$a$ が同じで $b$ が異なる $(A)$ の形の$2$直線、または $c$ が異なる $(B)$ の形の$2$直線のことをいいます。
前者の場合、$b_1 \neq b_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
y &=& ax+b_1 \\
y &=& ax+b_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
y_0 &=& ax_0+b_1 \\
y_0 &=& ax_0+b_2
\end{eqnarray*}
より $b_1=b_2$ が導かれるので、矛盾を生じます。
後者の場合、$c_1 \neq c_2$ に対して次の$2$直線を考えます。
\begin{eqnarray*}
x &=& c_1 \\
x &=& c_2
\end{eqnarray*}
これらがもし$1$点 $(x_0,y_0)$ を共有したと仮定すると、
\begin{eqnarray*}
x_0 &=& c_1 \\
x_0 &=& c_2
\end{eqnarray*}
より $c_1=c_2$ が導かれるので、やはり矛盾を生じます。以上で②が証明されました。
さて、$F_4$ 平面上の直線についてはさらに次の性質があります。
③ 各直線はちょうど $F_4$ の元の数（$4$個）の点を通る
これを示すために、$F_4 = \{ \, e_1, \, e_2, \, e_3, \, e_4 \, \}$ としたことを思い出しましょう。$(A)$ の形の直線 $y = ax+b$ については、
\[ (e_1, ae_1+b), \ (e_2, ae_2+b), \ (e_3, ae_3+b), \ (e_4, ae_4+b) \tag{1} \]
の$4$個の点を通り、それ以外は通りようがありません。また $(B)$ の形の直線 $x = c$ については、
\[ (c,e_1), \ (c,e_2), \ (c,e_3), \ (c,e_4) \tag{2} \]
の$4$個の点を通り、それ以外は通りようがありません。これで③が成り立つことがわかります。
直線に関する①②③の性質を使うと、麻雀大会組合せ問題が次のように解決されます。
まず、$a=e_1$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考え、これらの直線をそれぞれ雀卓に見立てます。性質③より各直線はちょうど$4$点を通り、それらは$(1)$を具体的に（ $F_4$ において）計算することによって特定できます。特定した各点にはそれぞれメンバーが割り当てられていますので、$4$台の雀卓にそれぞれ$4$人ずつのメンバーが割り当てられます。また、これら$4$本の直線は平行していますので、性質②より同じメンバーが$2$台以上の卓に割り当てられることはありません。従って、これで$16$人のメンバー全員が$4$卓を使って同時に半荘をプレイできることになります。
全卓が半荘$1$回終了したら、次に $a=e_2$ と固定し、$b=e_1,e_2,e_3,e_4$ とした $(A)$ の形の$4$本の直線を考えて同様に雀卓にメンバーを割り当てて半荘をプレイします。これが終わればまた $a=e_3, a=e_4$ として同様に続けます。最後に $c=e_1,e_2,e_3,e_4$ とした $(B)$ の形の$4$本の直線について$(2)$を用いて雀卓にメンバーを割り当てて半荘をプレイします。以上で同時に$4$卓ずつ$5$回、全部で$20$回の半荘がプレイされます。
そして、性質①によって、異なる$2$人のメンバーはちょうど$1$回だけ同じ卓に割り当てられます。
これで問題の要件を満足する麻雀大会の組合せを計画することができました。
この問題の解法をよく見ると、初めにことわったとおり、「 $F_4$ は$4$個の元を持つ体である」以上のことは何一つ使っていないことがわかると思います。ということは、例えば位数$8$の有限体 $F_8$ を使って、
「$64$人の選手が、$8$レーンあるプールを使って水泳大会を行う場合の、各々の選手が自分以外の全ての選手とちょうど$1$回だけ同時に泳ぐような組合せ」
を計画することも、麻雀大会と全く同じ方法で可能なわけです（この場合各選手は全部で$9$回泳ぐことになります。かなりしんどい。）。さらに一般に、$q$が素数のべきであれば位数$q$の有限体 $F_q$ が存在しますので、$q^2$ 人のメンバーが $q$ 人ずつ組になって行う何らかの大会（人狼ゲームでも何でも可）の組合せが $F_q$ を使って上記の方法で計画できることになります。
（前記事）
コメント 0