ChompゲームとHilbertの基底定理 - フィボナッチ・フリーク

今回はChompというゲームに関する小ネタです．

Chompは石を使って2人で遊ぶゲームです．石を $n\times m$ に並べます．プレイヤーは図のようにある1つの石を選んで，そこより右上にある石を全て取り去ります．これを交互に繰り返して，一番左下の石を取った方が負けです．

f:id:fibonacci_freak:20171020111249p:plain

実はChompは先手必勝であることを示すことができます（このブログで以前紹介した手法です。ぜひ考えてみてください）が，今回はその話ではなく，ゲームが有限の手数で終わるかどうかという点に着目します．

もちろんChompそのものは，有限個の石が一手ごとに減っていくわけなので，自明に有限手数で決着がつきます．

しかし，石が右と上方向に無限に続いているという設定にした「無限Chomp」を考えると話は難しくなります．果たして無限Chompは有限手数で決着がつくのでしょうか？

実は無限Chompは必ず有限の手数で終わることが証明できます．このことはもちろん初等的にも示せますが，今回は可換環論の定理であるHilbertの基底定理を使った証明を紹介したいと思います．

定理（Hilbertの基底定理）．Noether環上の多項式環はNoether環である．特に $\mathbb{C}[x_1,\dots,x_n$ ]はNoether環である．

最も左下の石を $0$ 行目 $0$ 列目として， $a$ 行目 $b$ 列目にある石を $(a,b)$ と呼び，多項式環の元 $x^ay^b\in \mathbb{C}[x,y$ ]を対応させます．

f:id:fibonacci_freak:20171020112834p:plain

さらに盤面の状態にイデアル $I$ を次のように対応させます．まず初めは $I=(0)$ とし，プレイヤーが $(a,b)$ をとったら $I$ を $I+(x^ay^b)$ に変化させます．すると常に次の関係が成り立つことがわかります：

$(a,b)$ が盤面から取り除かれている $\Leftrightarrow$ $x^ay^b\in I$ .

さて，前述のように $\mathbb{C}[x,y$ ]はNoether環であり，先ほどの考察より $I$ は真に大きくなり続けるので，ゲームが終わらなければ矛盾します．よってゲームは有限手数で終わります！

この証明は石のマスが3次元，4次元方向にも並んで（つまり $\mathbb{Z}^n_{\geq 0}$ 上に石が並んでいる），取る時も $a \in \mathbb{Z}^n_{\geq 0}$ を選んで $a+\mathbb{Z}^n_{\geq 0}$ を取り去るという「高次元無限Chomp」に対しても適用できます．