数戟管理委員会委員長　平等院公理　様

数学的戦戟（第00010192号）をここに報告致します。

数学的戦戟第00010192号（以下、本数戟）は、以下のように行われました。

日時：◯◯◯◯年◯月◯日、十三時五十六分〜十五時七分

場所：××大学、第二食堂（東京都△△区△△ □□-□）

形式；相互対戦型

題目；三山崩し

参加者：本条圭介、南條体

勝者：南條体

勝者報酬（南條体）：本条圭介の数学科学生連合の会員権および東京都数学科学生連合の会員権の放棄

勝者報酬（本条圭介）：南條体の笑顔

以下、本数戟の概要を詳細に記します。

****************

『三山崩し』

ルール：

　一試合ごとに、交互に場に置かれた石を取っていき、取れなくなった方がその試合の敗者。また、敗者でない方がその試合の勝者。より多くの試合で勝者となった方が数戟の勝者。

条件：

１.一度に異なる山から、石を取ってはならない。

２.少なくとも一つ以上は石を取らなくてはならない。

３.石を増やしたり、また取る行為以外で減らしてはならない。

４.先攻は、初戦はコインで決定し、以降は、前戦の勝者が後攻となる。

５.勝負は五試合行う。

場：

１.今回は、指定の湯のみを石として用いる。

２.四つの山に、それぞれ五、四、三、二の石を置く。

数戟結果：

勝者；南條体

敗者；本条圭介（五回戦降参）

結果の経緯報告：

　初めに、一枚の硬貨を上に投げその裏表により先攻後攻を決定する手法（以下、コイントス）の結果、南條体（以下、南條氏）が先攻となった。この時、コイントスに用いた硬貨が二つに割れたが、先攻の決定に支障は出ないと判断した。条件の通り、場には五、四、三、二の石が置かれた四つの山があった（図１参照）。

A:◯◯◯◯◯

B:◯◯◯◯

C:◯◯◯

D:◯◯

図１

先攻の南條氏は、図１のBの山から四つの石を取った。次に、後攻の本条氏は………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………。

　第五回戦、先攻の本条氏は、長い沈黙の後、降参の意思を表明した。本条氏は、第四回戦において、何やら胸に痛みを感じているような仕草をしていたため、健康上の不良のためかと判断し、再度、降参の意思を確認したが、訂正はなかった。そのため、第五回戦は、本条氏の棄権とし、勝者を南條氏、同時に三対二で数戟の勝者は南條氏に決定した。

数学的背景：

　以下に、本数戟の数学的背景を解説する。

　まず、この三山崩し（別名ニム）はゲーム理論における「不偏(impartial)」ゲームであり、すなわち、それぞれの場において、二人のプレイヤーの違いが、「先攻、後攻」の違いしかないゲームである。具体的には、三山崩しにおいては、各場において、例えば、

A:◯◯◯

B:◯◯

という場でプレイヤーX、Yがいる場合、もしXが先手のとき、AかBの好きな山から、石を取ることができるが、もしYが先手のときにも、同じようにAかBの好きな山から石を取ることができる。つまり、「先手と後手を入れ替えてもゲームの内容は変わらないという対称的なゲーム」ともいえる。それに対して、囲碁や将棋は、お互いの色や陣地が決まっているため、対称的なゲームではなく、不偏ゲームではない。このようなものは、非不偏(partial)ゲームと呼ばれる。

　話を三山崩しに戻す。実は、三山崩しは、場によって、「先手必勝」「後手必勝」が完全に決定するゲームである。さらに、三山崩しは、ニム和を計算することにより、「先手必勝」「後手必勝」を判定することができる。ニム和とは、二つの整数に対して、それぞれ二進数で表記し、その桁ごとに排他的論理和を実行するものである。具体例としては、３⊕２＝(１１⊕１０)_2＝(１)_2＝１などが挙げられる。三山崩しは、「山ごとの石の数のニム和」が０ならば「後手必勝」、０でなければ「先手必勝」であることが知られている。この証明は、参考文献[1]-[3]を参照されたし。[1]は石取りゲームについての定番の名著。[2]は最近出版されたので入手がしやすく読みやすい。[3]はネット上で無料で公開されている講義録である。また、ゲーム理論については、群城すず氏が、留学先のテキストで使われていたと、[4]を挙げていた。[4]にも三山崩しについて説明されている。

参考文献

[1]「石とりゲームの数理」一松信，数学ライブラリー教養篇，森北出版社，1968

[2]「石とりゲームの数学:ゲームと代数の不思議な関係」佐藤文広，数学書房，2014

[3]「ゲームの戦略– Nim って知ってますか？ –」内藤久資，１９９９年度名古屋大学数学公開講座，https://www.math.nagoya-u.ac.jp/~naito/lecture/high_school_1999/note.pdf

[4]「Game Theory, Alive」Yuval Peres，http://www.stat.berkeley.edu/~peres/gtlect.pdf

　以上が、「三山崩し」の数学的背景であったが、南條氏はこれを「ブール環」と関連付けた。本数戟の開催動機と関連があるため、補足として以下にそれを記載する。

　まず、ブール環とは、任意の元がべき等元（二乗しても不変な元）となる環である。ブール環は必ず、可換環となる。最も簡単な例としては、二元体F_2が挙げられる。南條氏は、本条氏にこれ以外のブール環の例の構成を要求していた。本条氏は最終的に、ニム和⊕とニム積⊗（ニム和の排他的論理和をANDにしたもの）が自然数の集合をブール環にすることに気づいた。自然数がこの演算でブール環となることは、すなわち、a,b,cを任意の自然数とすると、

1. (a⊕b)⊕c=a⊕(b⊕c)

2. a⊕0=a

3. -aが存在して，a⊕(-a)=0

4. a⊕b=b⊕a

5. (a⊗b)⊗c=a⊗(b⊗c)

6. a⊗1=a

7. a⊗(b⊕c)=(a⊗b)⊕(a⊗c)

8. (a⊕b)⊗c=(a⊗c)⊕(b⊗c)

9. a⊗a=a

がすべて成り立つことである。これは、この報告書の読者への演習問題とする。

　南條氏は、ブール環について、ニム和とニム積は、一見すると、不自然に演算を決めたようだが、実はよく見る集合の演算と同じであることに言及していた。例えば、三つの元からなる集合{A,B,C}を考えた時、その部分集合は、以下のように、全部で八つある。

{} (空集合)

{A}

{B}

{C}

{A,B}

{B,C}

{A,C}

{A,B,C}

ここで、三桁の二進数に対し、一桁目をA、二桁目をB、三桁目をCに対応させ、それぞれの部分集合に対して、A,B,Cを含んでいたら対応する桁を１、含んでいなかったら対応する桁を０と決めると、次のようになる。

{}　↔︎ ０００

{A} ↔︎ ００１

{B} ↔︎ ０１０

{C} ↔︎ １００

{A,B} ↔︎ ０１１

{B,C} ↔︎ １１０

{A,C} ↔︎ １０１

{A,B,C} ↔︎ １１１

ここで、部分集合同士の共通部分を考える。例とすれば、

{A,B}∩{B,C}={B}

であるが、一方、対応する二進数のニム積を考えると、

０１１⊗１１０＝０１０

であり、０１０に対応する部分集合は{B}であり、確かに、

{A,B}∩{B,C}={B}

⇅

０１１⊗１１０＝０１０

共通部分とニム積は全く同じ演算であることがわかる。

それでは、ニム和は、集合の場合、何に対応するか。それは、対称差△である。

対称差とは、和集合から、共通部分を引いたもので、例えば、

{A,B}△{B,C}=({A,B}∪{B,C})-({A,B}∩{A,C})={A,B,C}-{B}={A,C}

となる。一方、これもニム和で考えると、

０１１⊕１１０＝１０１

であり、１０１は{A,C}に対応していたので、確かに、対称差とニム和は同じものである。

　一般のn桁の二進数は、n個の元を含む集合の部分集合と一対一に対応する。すなわち、二進数全体というのは、自然数の有限部分集合全体と一対一に対応する。つまり、ニム和とニム積によってできたブール環は、自然数の有限部分集合全体と自然数全体に対称差と共通部分を入れたものと同じだったわけだ。

　ここで、任意の集合に対して、その部分集合全体に、同じように対称差と共通部分を考えられるため、好きなだけ多くのブール環を作ることができる。実は、ブール環というものは、このような部分集合によるブール環の部分環しかないというのが、南條氏が言及していたストーンの表現定理の主張である。

　最後に、ブーリアングレブナー基底について、ここに記す。そもそも、南城氏がブール環について話を始めた発端は、その先刻、本条氏と群城氏が行っていた「嘘つき問題*」(*別紙参照)である。群城氏は、二元体上の多項式環 F_2[x1,x2,x3...,xn] の連立方程式と、嘘つき問題を対応させていた。この時、連立方程式を解くためのグレブナー基底に x^2+1=0 などの式が登場する可能性があるが、x に入る数字としては０と１しかないため、x^2 は x と意味としてはまったく同じである。つまり、F_2上においては、

x^2+1=0 ⇔ x+1=0

であるわけだ。今、x^2の例を出したが、これは x^1000000 でも話は同じであり、

x^1000000+1=0 ⇔ x+1=0

つまり、同じ意味を持つ式の場合、より少ない次数の方が計算する上で便利であろう。そこで、x^2とxを同一視することを考える。簡単のため、多項式はx,yの二変数とすると、F_2[x,y]をイデアル(x^2-x, y^2-y)で割った剰余環

F_2[x,y]/(x^2-x, y^2-y)

が考えられる。環に不慣れな読者は、x^2とx、y^2とyを同一視する規則を入れたと考えれば良い。実は、これはブール環となっている。例えば、多項式 x+y を二乗してみると、

(x+y)^2=(x+y)(x+y)=x^2+2xy+y^2=x+0*xy+y=x+y

となっている(F_2では2=0である)。これをブール多項式環と呼ぶこととする。つまり、F_2[x,y]/(x^2-x, y^2-y)では、それぞれの変数の次数は２以上にならず、次数が小さいもので多項式が表現できることがわかる。この F_2[x,y]/(x^2-x, y^2-y) での、グレブナー基底が「ブーリアングレブナー基底」である。（一般には、ブール環Bに対して、B[x1,...,xn]/(x1^2-x1,...,xn^2-xn)のグレブナー基底をブーリアングレブナー基底と呼ぶ）

　まとめると、南條氏が主張したことは次の通りである。

嘘つき問題→連立方程式 in 普通の多項式 → グレブナー基底

⇦次数が大きくなるかも？

嘘つき問題→連立方程式 in ブール多項式環 → ブーリアングレブナー基底

⇦次数は、大きくならない！

　しかし、どのくらい早くなるかは、実際に計算機実験をしてみなければわからないだろう。

　また、以下にブーリアングレブナー基底の参考文献[5]，[6]を挙げる。

他にも、ブーリアングレブナー基底は、[7]のように「数独の解法」などに応用されているようである。

[5]「Boolean Gröbner bases」Yosuke Sato，Shutaro Inoue，Akira Suzuki，Katsusuke Nabeshima，Ko Sakai，Journal of Symbolic Computation，2011， http://www.sciencedirect.com/science/article/pii/S074771711000180X

[6]「ブーリアングレブナ基底を使用した集合制約解法の改良」井上秀太郎，数理解析研究所講究録，http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1907-13.pdf

[7]「ブーリアングレブナ基底を使った数独の解法」井上秀太郎他，数理解析研究所講究録，http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1666-01.pdf

以上で、本数戟の報告を終了とする。

◯◯◯◯年◯月◯日

文責；平等院命題