高橋　磐郎：組合せ理論とその応用

概要

http://www.katch.ne.jp/~four-seasons/tournaments/matching.html や http://math.a.la9.jp/league5.htm にあるような、 16 人麻雀の総当り問題がある。 この問題を試行錯誤によらず、 スマートに解きたい。どんな方法があるか。

前半は統計の実験計画法を、 後半は通信や情報の理論を例にとり、 ガロア体 `GF(2)` の理論と応用を明らかにする。

感想

この本を買ったのは、著者である高橋先生の授業で教科書として指定されたからである。 実は、この授業には一度も出たことがなかった。 にもかかわらず、試験を受けて優をいただいた。 高橋先生の顔を全く知らずに単位を得たので、申し訳ない気持ちでいっぱいである。

閑話休題、この本は本当に面白い。わたしはコンピュータを含めて理工学書を数十冊は買ったが、 この本を読んだ回数は抜群に多い。もっとも、何回も読んでそのたびに忘れるからということもある。

麻雀問題を巡って

はしがき

著者は次のように 16 人麻雀総当り問題を定義している。なお、後で単に麻雀問題と呼ぶこともある。

16 人で麻雀を 5 回戦行なう（各回で 4 卓ずつ延 20 組できる）とき， どの 2 人もちょうど 1 回ずつ顔が合うような集合を作れ．

この問題は 16 人の集合を `{0, 1, …，15} = Omega` としておくと， `Omega` の部分集合 `B_(ij)`の集まり
`B = {B_(11), B_(12), B_(13), B_(14); B_(21), B_(22), B_(23), B_(24); …;B_(51), B_(52), B_(53), B_(54);}`
でつぎの条件を満たすものをつくることに他ならない；

1. `B_(ij)`の大きさ（元の数）はすべて 4
2. `B_(i1) cap B_(i2) cap B_(i3) cap B_(i4) = Omega `
3. `Omega`の中の任意の二つの番号`m, n(m != n)` に対して` m in B_(ij), n in B_(ij)` なる `B_(ij)` が `B`の中にただ一つ存在する．

あとがき

著者はあとがきで、 16 人麻雀総当り問題がガロア体を用いることによってすぐ解けることに気付いたと思うと書いている。以下、引用する。

著者は次のように 16 人麻雀総当り問題を定義している。なお、後で単に麻雀問題と呼ぶこともある。

`GF(2^2)=F` の 2 次元空間 `F^2` のすべての点とすべての直線を考える． 点を人に，直線を麻雀卓に対応させればよいが，この際 4 本の平行直線を 1 回分の 4 卓と見ればよいのである．

うーん、これではわからない。`GF(2)=F` や `GF(3)=F` の巡回直線の作り方はわかったが、`GF(2^2)=F` の巡回の直線がわからない。

直交計画から

しかたがない。この本をもう一回勉強しなおすしかないか。そう思っていながら実行できず、本をパラパラとめくっていると 96 ページにある次の表が目に飛び込んできた。ただし、行のタイトルA～P は本にはなく、私がふったものである。 理由は、列をわかりやすくするためである。

もともとこの表は、実験計画の章にあるp.92 の問4⁵型要因計画で大きさ 4²=16，強さ 2 の直交計画を作れの解答である。

以下用語を説明する。 4⁵型要因計画とは、水準が 4 、因子が 5 の計画という意味である。 因子が 5 とは、相互に独立に変更できるパラメータの種類（たとえば、温度、時間、質量、触媒、速度など）が 5 つであるということ、 水準が 4 とは、その因子の中の段階が 4 つあるということである。温度は連続量であり、700 ℃、800 ℃、900 ℃、1000 ℃と変えられる。 触媒などは離散量（カテゴリカル・データ）であり、 触媒なし、触媒種類A, 触媒種類B, 触媒種類C のように決めることができる。 大きさとは実験の回数である。

強さ 2 の定義は少しややこしい。 因子F_i の水準がφであり、かつ因子F_j の水準がψであるとする。 また、因子F_i の水準数をs_i、 因子F_j の水準数をs_jとする。 i, j, φ, ψを決めれば実験の個数が決まる。 全体の実験数をこの個数で割った数が必ず s_i*s_j に等しいとき、この計画は大きさ 2 であるという。 上記の場合でいけば、 s_i = F_j = 4 であり、かつ総実験数が 16 であるから、16 / (4 * 4) = 1 となる。 さて、上の表は強さ 2 となっているだろうか。 なお、水準は∞, 0, 1, 2 の４段階であらわされていることに注意する。 つまり、この表では＊「任意の２因子F_i、F_jに対する、水準φと水準ψの組み合わせは少なくとも 1 回、かつまた 1 回のみどれかの実験で現れる。」

では、＊を検証してみよう。 まず、因子F₁が`ν_1`、因子F₂が`ν_2`とする。 そしてF₁の水準が1、そしてF₂の水準が2 である実験は何回目にあるかを見る。 ここでは、A から P までの 16 文字で規定している。さて、以上のを満たす実験はL の回があり、この回のみである。つまり、 強さ 1 が満たされている。これを、すべての因子と水準の組み合わせで見ていけばよい。実際、上表はどのような因子と水準を決めると、どこかの回で少なくとも１回、また１回のみ実験が該当することがわかる。

今までは因子と水準の立場から見たが、こんどは実験の立場からみたらどうだろうか。A から P を16人のそれぞれの人間とみなして、 水準∞, 0, 1, 2を卓とみなす。そうすれば、水準`ν_1, ν_2，…` がそれぞれ麻雀の 1 回戦、2 回戦、…を意味することになる。 そして、それぞれの人間を２人取り出しても、1 回戦から 5 回戦まで少なくとも 1 回は、そしてただ 1 回のみ卓を囲むことになる。 この表の見方の変換が正しいかどうかには証明が必要だろうが、私にはわからない。

原始既約多項式の利用

さて、上記の表はどのように導いたか。やはり上記の本まる写しだが、こうなる。

`GF(4)={0, 1, alpha, alpha_2}(alpha_2=1+alpha)`として，次の1次式はどの2つも`GF(4)`上一次独立である。

`ν_1=θ_1，ν_2=θ_2，ν_3=θ_1+θ_2，ν_4=θ_1+αθ_2，ν_5=α^2θ_2，`

ここで、`(θ_1，θ_2)` の組み合わせとして辞書式順序で 16 個の組を代入していく。具体的には、 `(0, 0), (0, 1), (0, α), (0, α^2), (1, 0), (1, 1), (1, α), (0, α^2), (α, 0), (α, 1), (α, α), (α, α^2), (α^2, 0), (α^2, 1), (α^2, α), (α, α^2)` をそれぞれ計算する。

まず、(0, 0) を計算しよう。これは明らかで`ν_1=ν_2=ν_3=ν_4=ν_5=0` である。ここでは、元αの指数として水準を表現する。 αのべき乗は通常の数では0にはならないので、ここでは指数を∞として表現するのがお約束である。

次に(0, 1) を計算しよう。これも明らかで`ν_1=0, ν_2=ν_3=1, ν_4=α, ν_5=α^2` である。指数として抜き出せば、 (∞, 0, 0, 1, 2) となる。

さらに(0, α) を計算しよう。これは普通に計算すれば`ν_1=0, ν_2= ν_3=α, ν_4=α^2, ν_5=α^3` となる。 ところが、`α^3 = α(α^2) = α(α + 1) = α^2 + α = α + 1 + α = 2α+1 = 1` (2 = 0 は消える）となり、`ν_5=1` である。したがって水準は (∞, 1, 1, 2, 0) となる。

次からも愚直に計算しよう。計 16 回計算すれば表が得られる。

それにしても、こんな機械的な計算で＊の性質が得られるとは、数学とは怖いものである。ここで、タイトルの原始既約多項式とは、 `α^2 = α + 1` のことを表す。

s 人麻雀の総当り

この総当り問題を拡張しよう、s 人が同時に卓を囲めるよう麻雀があったとする。さて、4 人麻雀と同じように、総当りはできるだろうか。 この問題は、s = `p^n`(pは素数, nは正の整数)の形のときはできるのである。 したがって、少ないほうから数えて、3 人、4 人、5人、7人、8人、9人のときはできる。他の 6人、10 人の場合は、私は知らない。

s が素数のとき

s が素数のときは素直である。原始既約多項式を考慮する必要はない。 仮に 3 人麻雀だとしよう。水準は 3 であり、大きさは `3^2` = 9 である。因子は 4 として GF(3)={0, 1, 2}として，一次独立な1次式4個を作る。

`ν_1=θ_1，ν_2=θ_2，ν_3=θ_1+θ_2，ν_4=θ_1+2θ_2`

ここで、`θ_1`と`θ_2` の組み合わせを辞書式順序で入れていく。数字は 3 の剰余系で評価する。

類推で、s が素数一般のときは、水準 s 、大きさ `s^2`、因子を (s+1) としてGF(s) = {0, 1, …、s-1} の一次独立な1次式 (s+1) 個を作る。

s が素数のべき乗のとき

s が素数のべき乗のときは、原始既約多項式を考慮する。 `GF(p^n) = {0, 1, …, (p-1)，α, α^2, …, α^(s-2)}` で構成する。 水準は s であるから、大きさは `s^2` である。因子は (s+1) として一次独立な1次式(s+1)個を作る。 αのべき乗が大きくなったときは、原始既約多項式を用いて次数を下げていけばよい。

その他

他にもこの本に関することを書きたいのだが、するとこれだけで人生を使い切ってしまいそうだ。ここで筆をおく。

関連

直交表作成ツール OAG
http://hyam.dip.jp/hiroshi/comp/oag/index.html
(Hayst法に関する）参考文献
http://hayst.com/reference.aspx

数式の記述

数式は MathJax を用いている。

まりんきょ学問所 ＞ 数学の本 ＞ 組合せ理論とその応用