岡です。稲葉さんとの共同研究です。右シフトゲームという、0 と 1 の列で遊ぶゲームの話をします。 どの局面でも、勝ち負けを決める Grundy 値が、一枚の絵から読み取れる、というのが今日の結果です。
今日の内容は三つです。ゲームのルール、答えとなる公式、そしてその公式がなぜ正しいか。 第 5 章の証明が一番難しいところですが、何を示すかは第 4 章で先に述べるので、飛ばしても全体はわかります。
目次です。ゲーム、勝ち負け、答え、証明の方針、証明の詳細、その他の結果、まとめの順に進みます。
第 1 章、ゲームのルールです。
局面は、0 と 1 が並んだ列です。例えば 1101。ここから、手の打ち方を見ていきます。
手は三つの操作でできています。まず、1 を一つ選びます。ここでは一番左の 1 を選びます。
次に、選んだ 1 を 0 にします。1101 は 0101 になります。
最後に、列全体を右に一つずらします。一番右の桁ははみ出して消えます。0101 は 010 になります。
まとめると、一手は「1 を一つ選んで 0 にし、右に一つずらす」です。1101 から 010 が得られました。
同じ 1101 から、真ん中の 1 を選ぶと、1001 を右にずらして 100 です。
右端の 1 を選ぶと、1100 を右にずらして 110 です。
つまり 1101 には三つの手があり、行き先は 010、100、110 です。1 の数だけ手があります。
二人が交互に手を打ちます。1 がなくなると手が打てません。手が打てなくなった人の負けです。
一手ごとに列は一桁短くなるので、ゲームは必ず終わります。1101、110、01、0 と短くなっていきます。
先頭の 0 は何も変えません。0110 と 110 は同じ手を持ち、同じように遊べます。だから 0 で始まる列は、 先頭の 0 を取り除いて考えてかまいません。
第 1 章のまとめです。局面は 0 と 1 の列、手は 1 を選んで 0 にして右にずらすこと。 手が打てない人が負けで、ゲームは必ず終わります。
第 2 章、どちらが勝つか、です。
例えば 110 から始めたら、手番の人は勝てるでしょうか。
110 には 1 が二つあるので、手は二つ。行き先は 01 と 10 です。
01 も 10 も、1 が一つだけなので手は一つで、どちらも 0 になります。
0 には 1 がないので、手番の人は動けず負けです。L を付けます。L は「手番の人の負け」です。
01 と 10 からは、相手を負けの局面 0 に送れるので、手番の人の勝ちです。W を付けます。
110 からは、どう動いても相手が勝つ局面になります。だから 110 は手番の人の負けです。
ルールにすると、L は「どの手も W に行く」局面、W は「L に行く手がある」局面です。 動けない局面は L。終わりの方から順に決めていけます。
では 1101 はどうでしょう。
1101 の行き先は 010、100、110 でした。110 は今見たとおり L です。
010 と 100 は 1 が一つで、手は一つ、行き先は 00 です。00 は動けないので L。 だから 010 と 100 は W です。
1101 からは L の 110 に動けるので、1101 は W です。勝つには、右端の 1 を選んで 110 にすればよい。
ところで、列が二つ並んでいて、毎回どちらか一つに手を打つ、という遊び方もできます。 10 と 10 を並べてみます。10 は単独なら W でした。
先手がどちらかを 0 にすると、残りは 0 と 10。後手がもう一方を 0 にすると、先手は動けません。
W と W を並べると L になりました。勝ち負けだけでは、組み合わせたときの結果がわかりません。 そこで、各局面に一つの数を割り当てます。Grundy 値です。
Grundy 値の計算には mex を使います。リストにない一番小さい数です。{0} なら 0 があるので、1 が mex です。
{1, 1} なら、0 がないので mex は 0 です。
{0, 1, 1} なら、0 と 1 があって 2 がないので、mex は 2。
空のリストなら、mex は 0 です。
Grundy 値の定義です。行き先の値を全部集めて、その mex を取ります。動けない局面は 0 です。
1101 の木に値を付けていきます。動けない局面、0 と 00 の値は 0 です。
01 と 10 は、行き先の値が 0 だけなので、mex{0} = 1 です。
010 と 100 も、行き先 00 の値が 0 なので、値は 1。
110 は、行き先 01 と 10 の値が 1 と 1 なので、mex は 0。
そして 1101 は、行き先の値が 1、1、0 なので、mex は 2。1101 の Grundy 値は 2 です。
値 0 の局面は、さっき L と判定した局面とちょうど一致します。値 0 は手番の人の負け、値が 0 でなければ勝ちです。 値 0 の行き先に動くのが勝ち手で、1101 なら 110 に動く手です。
Grundy 値があれば、並べたときの勝敗がわかります。手番の人が負けるのは、各列の値の XOR が 0 のとき、 ちょうどそのときです。10 と 10 は 1 XOR 1 で 0、さっき見たとおり負けです。
同じ計算を、8 桁の列すべて、256 個についてやってみました。値を色と数字で並べています。 枠は 1101 と 11111 です。
何か気づくことはありますか。
値は 0、1、2、3 しか出てきません。8 桁の列には最大 8 つの手があるので、もっと大きな値もありえたはずです。
まず素朴な予想。1 の個数で値が決まるでしょうか。11 と 110 はどちらも 1 が二つですが、値は 2 と 0 で違います。 1 の個数だけでは決まりません。位置が効いています。
では、列から値を直接読み取れるでしょうか。読み取れます。それが今日の結果です。
第 3 章、答えです。
先に答えを言います。各列から M という数を一つ計算します。M が偶数なら値は 0 か 1、奇数なら 2 か 3 です。 どちらになるかは、M を 4 で割った余りか、ある一本の行の幅で決まります。ゲームの木を調べる必要はありません。
M の求め方を三つに分けて説明します。まず列を絵にします。
列を絵にするために、まず 1 の「寿命」を考えます。1101 を、何も選ばずに右シフトだけ繰り返してみます。 点線が右端です。
1 回シフトすると、一番右の 1 が右端から落ちます。もう 1 回シフトすると 11 になります。
3 回目で真ん中の 1 が、4 回目で一番左の 1 が落ちます。
1 が落ちるまでのシフトの回数を、その 1 の寿命と呼びます。1101 の 1 の寿命は、左から 4、3、1 です。 寿命は、その 1 から右端までの桁数、自分も含めて、に等しいです。
各 1 を、寿命の長さの横棒にします。長い順に、下から積みます。1 はそれぞれ違う場所にあるので、 長さはすべて違います。
11111 なら、寿命は 5、4、3、2、1 で、階段の形になります。今日は 1101 と 11111 をずっと例として使います。
手は絵ではどう見えるでしょうか。1101 で真ん中の 1 を選びます。対応するのは長さ 3 の行です。
一つ目。選んだ 1 は 0 になるので、その行は消えます。
二つ目。ほかの 1 は右シフトで寿命が 1 減るので、どの行も一マス短くなります。左の壁の外に出たマスが消える、 と描きます。長さ 1 の行は消えます。
残ったのは長さ 3 の行一本。これは 100 で、文字列で計算した手と一致します。
もう一つ。11111 で真ん中の 1 を選びます。消える行に ✕、その下の行は左へ、上の行は左下へ動きます。 上の行は、消えた行の隙間に落ちてくるからです。
動かすと、残るのは 4、3、1。つまり 1101 です。11111 から真ん中の 1 を選ぶと 1101 になる、という手と一致します。
まとめると、絵の上の手は、選んだ行を消して、下の行は左、上の行は左下にずらし、壁の外に出たマスを消すことです。
次に、マスに数を書きます。
次に、階段の形をしたマス目を用意します。段 y には 2y + 1 個のマスがあります。 階段の右側の灰色の部分は使いません。
左下のマスに 0 を書きます。
一つ上のマスは 2 大きく、一つ右のマスは 1 大きくします。だから 1 段目は 2、3、4 です。
2 段目は 4 から 8 まで。
全部書くとこうなります。マス (x, y) の数は 2y + x です。同じ数が何か所かに出てくることもあります。 例えば 4 は、1 段目と 2 段目にあります。
この上に、1101 の絵を置きます。隠れたマスの数も、白い文字で読めるようにしておきます。 隠れていない白いマスにも数が書いてあります。
M は、白いマスに書かれた数のうち一番小さいものです。0 から順に、白いマスにあるかを見ます。 0 は灰色のマスにしかありません。1 はどのマスにもありません。2 と 3 も灰色です。
4 は二か所にありますが、どちらも灰色です。同じ数が何か所かに出てくることがあるので注意します。
5 は白いマスにあります。だから M = 5 です。
定義です。M は、絵に隠されていない白いマスに書かれた数の最小値です。
いくつか例を見ます。1 が一つもない列では、何も置かないので 0 が白いままです。M = 0 です。
1 だけの列は、左下のマスだけを隠します。1 はどのマスにもないので、白いマスの最小は 2。M = 2 です。
11111 では、0 から 6 までの数はすべて灰色です。7 は二か所にあり、上の 7 は隠れていますが、 下の 7 は白いマスです。だから M = 7 です。
最後に、M から値を読み取ります。
M が偶数のとき。4 の倍数なら値は 0、4 で割って 2 余るなら値は 1 です。110 は M = 4 で値 0、 1 だけの列は M = 2 で値 1 です。
M が奇数のときは、一本の行を見ます。T = (M − 1)/2 とおき、高さ T の行を臨界行と呼びます。 1101 は M = 5 なので T = 2。高さ 2 の行、点線の枠の行です。
臨界行の幅が奇数なら値は 2、偶数なら値は 3 です。1101 の臨界行は幅 1 で奇数なので、値は 2。 第 2 章で木を書いて求めた値と一致します。
11111 は M = 7 なので T = 3。高さ 3 の行の幅は 2 で偶数なので、値は 3 です。
確かめます。11111 の五つの行き先の値は 0、0、2、1、1 です。mex は 3 で、公式と一致します。
いくつかの列で、公式の値と、ゲームの木で計算した値を並べました。全部一致しています。
8 桁の列 256 個すべてについて公式で値を計算すると、第 2 章でゲームの木から求めた表とぴったり一致します。
そしてこれは、すべての長さの列で成り立つ、というのが定理です。次の章から、なぜ成り立つのかを説明します。
第 3 章のまとめです。1 を寿命の棒にして積み、番号付きの盤に置いて、白いマスの最小の数を M とする。 M が偶数なら 4 で割った余り、奇数なら臨界行の幅の偶奇で値が決まります。
一枚だけ覚えるなら、この絵です。最後にもう一度出します。
第 4 章では、公式がなぜ正しいかの方針を説明します。細かい証明は第 5 章に回します。
まず、ゲームの途中で M がどう変わるかを見ます。
一つのゲームの例です。11111 から始めます。M は 7 です。
最後の 1 を選ぶと 1111、M は 6。1 減りました。
続けます。011 で M は 3、3 減りました。01 で 2、最後は 0 で M も 0 です。 減り方は 1、3、1、2 でした。
11111 からの五つの手を全部見ると、行き先の M は 4、4、5、6、6。減り方は 3、3、2、1、1 です。
これは偶然ではありません。一つ目の事実、Fact A です。どんな手でも、M はちょうど 1、2、3 のどれかだけ減ります。 証明は第 5 章で絵を使ってします。
1 から 3 だけ減る。どこかで聞いたことのあるゲームに似ています。
石取りゲームです。
石の山があります。交互に、1 個、2 個、3 個のどれかを取ります。取れなくなった人の負けです。
石が n 個のとき、手番の人が勝つか負けるかを、小さい方から決めます。0 個なら取れないので負け、L です。
1、2、3 個なら全部取れば相手が 0 個で負けるので、勝ち、W です。
4 個は、どう取っても 3、2、1 個が残り、相手が勝つ。だから負け、L です。
5、6、7 個は、4 個を残せば勝ち。8 個はまた負け。4 個ごとに繰り返します。
つまり、手番の人が負けるのは、石の数が 4 の倍数のとき、ちょうどそのときです。
なぜこうなるか。理由は二つです。一つ、4 の倍数からは、どう動いても 4 の倍数でないところへ行く。 二つ、4 の倍数でないところからは、4 の倍数へ行く手がある。この二つがあれば、 4 の倍数の側が負け続けることになります。
では M を石の数と思ってみます。
M を石の数だと思います。Fact A から、M が 4 の倍数なら、どう動いても 1 から 3 減るので、 4 の倍数ではなくなります。理由の一つ目は成り立ちます。二つ目には、もう一つ事実が必要です。
二つ目の事実、Fact B です。M が奇数なら、ちょうど 1 減らす手と、ちょうど 3 減らす手がある。 M が 0 でない偶数なら、ちょうど 2 減らす手がある。
例です。11111 は M = 7 で、M が 6 の 1111 と、M が 4 の 0111 に行けます。1111 は M = 6 で、 M が 4 の 110 に行けます。
どの M からでも、4 の倍数でなければ、Fact B の手で 4 の倍数に行けます。奇数なら 1 か 3 減らして、 4 で割って 2 余るなら 2 減らして。これで理由の二つ目も成り立ちます。
二つの理由がそろったので、石取りと同じく、手番の人が負けるのは M が 4 の倍数のとき、ちょうどそのときです。 110 は M = 4、111101 は M = 8 で、どちらも負けの局面です。
次は勝ち負けだけでなく、Grundy 値を決めます。まず値 0 と 1 です。
M の小さい方から値を決めていきます。値は、行き先の値の mex でした。M = 0 は 1 が一つもない列で、 手がないので値 0 です。M = 1 の局面はありません。1 が書かれたマスがないからです。
M = 2。Fact A より、行き先の M は 1 から 3 小さいので、0 か 1。M = 1 はないので 0、値 0 の行き先があります。 値 1 の行き先はないので、mex は 1。
M = 3。Fact B より、1 減らす手と 3 減らす手があります。M = 2 の値 1 と、M = 0 の値 0。 0 と 1 がそろうので、値は 2 以上です。
M = 4。行き先は 3、2、1 のどれか。値は 2 以上か 1。0 がないので、値は 0。
M = 5。1 減らして 4 へ行くと値 0、3 減らして 2 へ行くと値 1。だから値は 2 以上。
M = 6。2 減らして 4 へ行くと値 0。ほかの行き先は 5 か 3 で、値は 2 以上。1 がないので値 1。
同じことが 4 個ごとに繰り返します。4 の倍数は値 0、4 で割って 2 余るなら値 1、奇数なら値 2 以上。
まとめると、Fact A と B から、偶数の M については公式の値が出ます。残るのは奇数の M で、2 か 3 か、です。
奇数の M で、値が 2 か 3 かを決めます。
M が奇数なら、値 0 と 1 の行き先は必ずあります。だから値は、値 2 の行き先がなければ 2、 値 2 の行き先があって値 3 の行き先がなければ 3 です。
値 2 以上の行き先は、M が奇数の行き先だけです。奇数から奇数へ、1 から 3 だけ減らすには、 ちょうど 2 減らすしかありません。
1101 は M = 5。行き先の M は 2、2、4 で、奇数の行き先がありません。値は 1、1、0 で、2 がないので値 2 です。
11111 は M = 7。奇数の行き先は 1101 だけ、M = 5 で値 2。値 0、1、2 がそろい、3 がないので値 3 です。
何が値 2 の行き先の有無を決めるのか。臨界行です。Fact C。M が奇数で、ちょうど 2 減らす手では、 臨界行の幅の偶奇が必ず変わります。11111 の臨界行は幅 2、行き先 1101 の臨界行は幅 1 です。
Fact D。M が奇数で臨界行の幅が偶数なら、ちょうど 2 減らす手があります。11111 から 1101 がその手です。
これで二つの場合が決まります。臨界行の幅が奇数なら、2 減らす行き先は幅が偶数になり、M の小さい方からの 帰納法で値は 3。値 2 の行き先はないので値 2。
幅が偶数なら、Fact D で 2 減らす手があり、Fact C で行き先の幅は奇数、値は 2。値 3 の行き先はないので、値 3。 これが公式の奇数の場合です。
ここまでの方針を一枚の図にまとめます。
Fact A と B から偶数の M の値と、奇数なら 2 以上が出ます。それに Fact C と D を加えると、奇数の場合が決まり、 主結果になります。全体は M の小さい方からの帰納法です。
つまり、残る仕事は、一手で絵がどう変わるかについての四つの事実を示すことだけです。
第 5 章で、この四つを一つずつ、絵で証明します。チェックを一つずつ埋めていきます。 第 5 章は一番難しいので、飛ばして第 6 章に進んでも大丈夫です。
第 5 章、証明です。一番難しいところなので、飛ばして第 6 章に進んでもかまいません。
道具を三つ用意してから、Fact A、B、C、D を順に示します。右上のチェックが、示し終えた事実です。
道具 1。M の意味の言いかえです。11111 は M = 7 でした。これは、0 から 6 までの数が書かれたマスが すべて隠れていて、7 が書かれたマスのどれかが白い、ということです。0 から 6 を隠しているタイルを濃い色にしました。
道具 2。各行で、タイルのすぐ右の最初の白いマスを、その行の行末と呼びます。枠で囲みました。 何もない行は、最初のマス 2y が行末です。階段の外の行末は点線で、使いません。M は行末の中で一番小さい数です。 11111 では 7、8、9、10 の中の 7。
道具 3。タイルが動くと、隠す数が変わります。マスの数は 2y + x でした。左に一つ動くと 1 小さい数を、 左下に一つ動くと、2 と 1 で 3 小さい数を隠します。この 9 のタイルなら、左で 8、左下で 6 です。
道具 4。一つの局面からの行き先を並べます。11111 には五つの手があり、消す行を下から上へ変えると、 行き先の M は 4、4、5、6、6 です。
五つを一つの盤に重ねます。濃い部分が一番下の行を消した行き先。消す行を一つ上にするたびに、 マスが増えるだけです。+k は、行 k − 1 の代わりに行 k を消すと増えるマスです。どの行き先も、前の行き先を含んでいます。
なぜか。行 1 を消す場合と行 2 を消す場合を比べます。違うのは高さ 1 の行だけです。行 1 を消すと、 元の行 2 が左下から来ます。行 2 を消すと、元の行 1 が左にずれて残ります。下の行ほど長いので、 後者の方がマスが多い。ほかの高さは同じです。
マスが増えると、隠れる数が増えるだけなので、M は増えるか同じです。だから、どの手の M′ も、 一番下の行を消した手と、一番上の行を消した手の間にあります。11111 なら 4 と 6 の間です。
Fact A を示します。どの手でも M は 1 から 3 減る。下限と上限に分けます。
まず、一番下の行を消す手。道具 4 より、これが M′ の一番小さい手です。ほかの行はすべて左下にずれます。 0 から 6 を隠している濃いタイルの行き先を見ます。
動かすと、左下にずれたタイルは 3 小さい数を隠します。0 から 6 を隠していた濃いタイルは、0 から 3 を隠します。 4 は白くなります。行き先 0111 の M′ は 4、ちょうど 3 減りました。
一般に、M − 3 より小さい数 n のマスを考えます。その右上のマスは n + 3 で、階段の内側にあり、M より小さいので 隠れていました。左下にずれると、そのタイルが n を隠します。だから M − 3 より小さい数はすべて隠れたまま。 M′ ≥ M − 3 です。ほかの手は道具 4 でもっと大きいので、どの手でも M′ ≥ M − 3。
次は一番上の行を消す手。M′ の一番大きい手です。ほかの行はすべて左にずれます。
M = 7 の行が一マス短くなるので、すぐ左の 6、つまり M − 1 が白くなります。だから M′ は M − 1 以下。実際 6 です。
特別な場合が二つあります。M が消した一番上の行そのものにあるとき。11 なら、空の行が下りてきて、 その最初のマス 2 が白くなります。M が空の行の最初のマスにあるとき。10 なら、空の行が一段下りて 0 になります。 どちらも M′ ≤ M − 1 です。
どの手でも、M − 3 ≤ M′ ≤ M − 1。Fact A が示せました。
Fact B の準備として、行が左にずれたときに、どんな白いマスが新しくできるかを調べます。
1101、M = 5 で、一番上の行を消します。ほかの行は左にずれます。新しく白くなるマスはどこか。
新しく白くなったのは二つ。高さ 1 の右端の 4 と、高さ 2 の最初のマスの 4 です。M′ = 4 です。
一つ目。普通のマスは、右隣のマスのタイルが左にずれてきて隠されます。右隣の数は 1 大きい。 それが M より小さければ隠れていたので、このマスも隠れたままです。だから、普通のマスで新しく白くなるのは M − 1 以上だけです。
二つ目。階段の端のマス、数 4y、には内側の右隣がありません。ここは別に考えます。端のマスが白くなるのは、 その行の最後のタイルがちょうど端のマスにあったとき、つまり幅が 2y + 1 のときだけです。1101 では高さ 1 の行がそうで、 端の 4 が白くなりました。
そのとき、すぐ上の行は短いので、行末は e + 2 以下にあります。ここでは e = 4、上の行末は 5 で、6 以下。 M は行末の最小なので M ≤ e + 2、つまり e ≥ M − 2。しかも e = 4y は偶数です。
三つ目。消した一番上の行の上にあった空の行は、一段下りてきます。その最初の数は、M 以上だったものが 2 減るだけ。 1101 なら 6 が 4 になりました。これも偶数で、M − 2 以上です。
まとめます。左にずれたあとで新しく白くなるマスの数は、M − 1 以上か、偶数なら M − 2 もありうる。 M − 3 以下は決して白くなりません。これをスライド補題と呼びます。
M − 2 が実際に起きる例です。1111 は M = 6。一番上の行を消すと、高さ 1 の行がちょうど端で終わっていたので、 端の 4 = M − 2 が白くなります。111、M′ = 4 です。
ここで M は偶数でした。M が奇数なら M − 2 は奇数なので、新しく白くなるのは M − 1 以上だけです。
Fact B を示します。
M が奇数のとき。左端の列の数 2y と、階段の端の数 4y は偶数です。だから奇数の M のマスはそのどちらでもなく、 その左下のマスも階段の内側にあって、M − 3 が書かれています。
一番下の行を消すと、すべて左下にずれます。M のマスは白かったので、そこへ来るタイルはありません。 だから M − 3 のマスは白いまま。M′ ≤ M − 3、Fact A とあわせて M′ = M − 3。7 から 4 です。
次に一番上の行を消す手。Fact A の証明で、M′ ≤ M − 1 でした。
スライド補題より、新しく白くなるのは M − 1 以上か、偶数の M − 2 だけ。M が奇数なので M − 2 は奇数。 だから M − 1 より小さい白いマスはできず、M′ = M − 1。7 から 6 です。
M が偶数のとき、ちょうど 2 減らす手を作ります。梯子の手と呼びます。例は 111101、M = 8。 まず行末の性質です。一つ上の行へ行くと、数は 2 増えますが、行は 1 マス以上短くなります。だから、 空でない行から一つ上へ、行末は高々 1 しか増えません。8、9、9、10 です。
M を行末に持つ一番上の行を h と呼びます。行 h が空でない場合と、空の場合に分けます。空でない場合は、 これから見る梯子の手。空の場合は最後に見ます。
場合 1、行 h が空でないとき。111101 では h = 2 です。そのすぐ上、高さ 3 の行末はどこか。行 h + 1 は行 h より短いので、 その行末は階段の内側にあります。M より小さいところはだめ、M が最小だから。M ちょうどもだめ、h が一番上だから。 M + 1 より大きいところもだめ、行 h は空でないので高々 1 しか増えないから。残るのは 9 = M + 1 だけです。
9 は奇数です。空の行の行末は最初のマス 2y で偶数。だから高さ 3 の行は空ではありません。
高さ 2 の行を消します。すぐ上の行は左下にずれ、その行末 9 は 3 減って 6 = M − 2 になります。 短い行なので階段の内側です。
ほかの行末はどうか。行 h より上の行は行 h より短いので、行末は階段の内側にあり、M ではないので M + 1 以上でした。 3 減っても、空の行なら 2 減っても、M − 2 以上。下の行は左にずれるだけなので、スライド補題の (i)、(ii) で M − 2 以上。 だから M′ = M − 2。11010、M′ = 6 です。
まとめます。M を行末に持つ一番上の行を h とする。そのすぐ上の行が空でなければ、行 h を消す手で M′ = M − 2。 これを梯子の手と呼びます。Fact D でもう一度使います。
場合 2、行 h が空のとき。M はその空の行の最初のマスです。このときは一番上の行を消せば、空の行が一段下りて M − 2 が白くなります。スライド補題より、M − 2 より小さい数は白くなりません。10100 なら 4 から 2。
これで Fact B が示せました。M が奇数なら 1 減らす手と 3 減らす手、偶数なら 2 減らす手があります。
Fact C を示します。臨界行の偶奇が反転すること。
Fact C の前に一つ準備。M が奇数のとき、臨界行は空ではありません。空なら、その最初のマス 2T = M − 1 が白くなり、 M が最小であることに反します。
M が奇数の局面から、M が奇数の行き先へ行く手は、Fact A より、ちょうど 2 減らす手です。11111 では、 行 2 を消す手だけで、これは臨界行 T = 3 より下の行です。
なぜか。臨界行は 2T = M − 1 から始まるので、M − 2 は臨界行より下にしかありません。臨界行かそれより上の行を 消すと、臨界行より下の行は左にずれるだけ。M − 2 は奇数なので端の数でも空の行の数でもなく、スライド補題の (i) で、 右隣の M − 1 のタイルが来て隠れたままです。
だから 2 減らす手は臨界行より下の行を消します。すると臨界行は左下にずれて、一マス短くなり、高さ T − 1 に来ます。 新しい M は M − 2 なので、新しい臨界行の高さは (M − 3)/2 = T − 1。ちょうどこの行です。
11111 から 1101 では、幅 2 の臨界行が幅 1 になりました。幅がちょうど 1 減るので、偶奇が反転します。Fact C です。
最後に Fact D です。
M が奇数で、臨界行の幅が偶数のとき、ちょうど 2 減らす手があることを示します。幅が偶数なので 2 以上。臨界行は M − 1 と M を覆うので、その行末は M + 1 以上。上の行は M + 1 以上から始まる。 だから臨界行から上の白いマスはすべて M + 1 以上です。緑で塗りました。M を行末に持つ行は、臨界行より下にあります。
臨界行までの行はすべて空ではありません。M を行末に持つ一番上の行 h は臨界行より下なので、そのすぐ上の行も 空ではない。梯子の手の条件がそろいました。
行 2 を消すと、すぐ上の行の行末 8 が左下にずれて 5 = M − 2。11111 から 1101 への手が、ちょうど 2 減らす手です。 Fact D が示せました。
四つの事実がすべて示せました。第 4 章の方針と合わせて、主結果の証明が完成です。
つまり、どんな列でも、Grundy 値は M と臨界行の幅から読み取れます。
第 6 章、その他の結果です。
まず、勝つ手の見つけ方です。
勝つには、値 0 の局面、つまり M が 4 の倍数の局面に動けばよい。1101 なら、行き先の M は 2、2、4。 4 の 110 に動く、右端の 1 を選ぶ手が勝ち手です。
では、全部の行き先の M′ を速く求められるか。行が r 本なら手は r 個。一つずつ計算すると、 長さ L の列で L × r の手間です。実は、一回ずつの走査でまとめて求まります。
11111 で見ます。行き先の各高さに来る行は二通りしかありません。消した行より下なら、その高さの行が左にずれて残る。 消した行の高さ以上なら、一つ上の行が左下にずれて来る。その二通りの行末を、先に A と B の列にしておきます。
行 2 を消す手では、高さ 0 と 1 は A、高さ 2 から上は B を使い、その中の最小が行き先の M′ です。 A の 0 と 1 は —、B は 5、6、8 なので、M′ = 5。
どの c についても、A の下からの最小と、B の上からの最小の小さい方です。下からの最小と上からの最小は、 それぞれ一回の走査で全部作れます。だから全部の M′ が、行の数に比例する手間で求まります。11111 なら 4、4、5、6、6。
まとめると、長さ L の列から、値と、あれば勝ち手が、L に比例する手間で求まります。M′ が奇数の行き先は、 臨界行が元の行のずれたものなので、値もすぐに分かります。これは証明済みの定理です。
次はミゼール、最後に動いた人が負けのルールです。
ミゼールでは、最後に動いた人が負けです。M の数直線で考えます。M = 0、1 が一つもない列では手がないので、 手番の人は、相手が最後に動いたことになり、勝ちです。
M = 2 からは、行けるのは M = 0 だけ。1 のない列にするしかなく、自分が最後に動いたので負けです。
M = 6 からは 5、4、3 に行きます。でも相手は、5 から 3 減らして、4 から 2 減らして、3 から 1 減らして、 また 2 に戻せます。Fact B の手です。だから M = 6 も負け。10 も同じです。
まとめると、ミゼールで手番の人が負けるのは、M を 4 で割って 2 余るとき、ちょうどそのときです。 通常ルールの 0 と入れ替わった形です。値まで含めた詳しい形は予備スライドにあります。
次は、ランダムな列での値の割合です。
長さ L の列を全部数えて、各値の割合を出しました。L = 20 でも、値 0 が 3 割、値 3 は 2 割弱と偏っています。
それでも、長さを大きくすると、四つの値はそれぞれ 4 分の 1 に近づくことを証明しました。 ただしデータでは近づき方はゆっくりで、速さは証明していません。
証明のアイデアだけ紹介します。列を左から読み、1 の数から 0 の数を引いたものを Z とすると、ランダムウォークです。 ピンクの線は、Z と紺の直線の大きい方。M は L とその最低点の和になります。最低点は列の後半にあり、 そこでのランダムな上下で M を 4 で割った余りがほぼ均等に、最後の方の桁で臨界行の幅の偶奇がほぼ均等になります。 詳細は論文と予備スライドです。
最後に、どこまで確かめたか。
論文の定理と補題はすべて Lean 4 という証明支援系で検証しました。これが主定理の主張です。ピンクは手のルールと mex を そのまま書いたもので、そういう関数が存在することも証明しています。紺が M、黒が値の表です。
論文の 11 個の定理と補題すべてを、47 個の形式的な主張として書き、抜けなしで検証しました。ただし、主張が論文と 一致しているかの確認と、計算時間の数え方の確認は AI によるレビューで、人間による独立のチェックはまだです。
まとめです。
第 3 章で見た一枚の絵をもう一度出します。1 を寿命の棒にして階段の盤に置き、白いマスの最小の数が M。 M を 4 で割った余りと、臨界行の幅の偶奇で値が決まります。
主結果です。各列から M を計算すれば、値はゲームの木なしで決まります。
証明は、一手で M がどう変わるかについての四つの事実から、石取りゲームと同じ議論で偶数の場合を、 臨界行の偶奇の反転で奇数の場合を決めました。四つとも、絵で証明しました。
ほかに、線形時間で勝ち手が求まること、ミゼールの負け局面、ランダムな列で値が 4 分の 1 ずつになること、 Lean での検証を紹介しました。Lean の主張の一致は AI のレビューのみ、という但し書きがあります。
今後の課題です。数字 2 も含む列のゲーム、つまり一つの桁を 1 減らしてから右シフトするゲームでは、 一般の規則はまだ分かっていません。
ありがとうございました。
関連するゲームとの比較です。Welter のゲーム、佐藤の Maya ゲームは局面は同じ自然数の有限集合ですが、手が違います。 MARK は 1 を引くか半分にするゲーム。ここでは 1 を消して半分にするのを一手で行います。LCTR や CRIM は 行か列を消すゲームですが、ここでは両方を同時に行います。1〜3 個の石取りとは、負け局面は一致しますが値は違います。
ミゼールの値は、通常の値の 0 と 1 を入れ替えたものです。空でない値 0 の局面から値 1 の局面へ必ず動けることが鍵で、 これは Fact B の 2 減らす手から出ます。
1/4 の証明の概略です。上の桁から読んだランダムウォークで M = L + min max(Z_k, L − 2k)。最小値は高い確率で窓の中にあり、 M の 4 の余りは均等に、臨界行の位置は幾何分布の和なので偶奇が半々に近づきます。収束の速さは証明していません。
Lean の詳細です。主張と証明は別ファイル、公理は標準の三つだけ、lean4checker で再検査しています。 主張の一致は AI のレビューのみで、人間のレビューの記録はまだありません。計算時間はカウンタについての定理です。
整数で書くと、2 の i 乗の位の 1 を選ぶ手は、n から 2 の i 乗を引いて 2 で割って切り捨てる、です。 どの手でも n は減るので、ゲームは必ず終わります。