$\mathrm{Nim}_K$ のお気持ち証明メモ
経緯
学校の数学テーマ学習で、なんやかんやあって $\mathrm{Nim}_K$ についての研究（？）をすることになりました。
班員 $1$ が先行研究を見つけてきて、班員 $2$ であるところの Forested が証明込みの この記事 を持ってきてくれたのですが、証明の解読に時間がかかりました（結局解読に成功した Forested に教えてもらいました）。
あとで思い出したときなどのために、メモ的なものとしてお気持ちを記しておきます。直感的な理解のために利用してください。厳密性は全く気にしません。
$\mathrm{Nim}_K$ の概要
$\mathrm{Nim}_K$ とは、以下のようなルールで行われる二人零和有限確定完全情報ゲームです：
- 石の山を $N$ 個用意する。各山の石の個数を順に $A_1,A_2,\ldots,A_N$ とする。
- 自身の手番において、各プレイヤーは以下のような操作を行う。
- 山を $1$ 個以上 $K$ 個以下 任意に選択する。
- 選んだそれぞれの山について、$1$ 個以上任意の個数取る。
- 最後の石を取った方の勝ちである。
例えば、一般的な Nim は、$\mathrm{Nim}_1$ に相当します。
さて、このゲームの勝敗判定を高速に行いたいです。何か良い方法はないものでしょうか。一般的な Nim は、XOR を利用していましたが……
$\mathrm{Nim}_K$ の勝敗判定法
天下り的にも程がありますが、結論から言えば、以下のような方法で勝敗を判定することが出来ます：
- まず、$A_1,A_2,\ldots,A_N$ を二進数（というか、$01$ 列）に変換したものを $B_1,B_2,\ldots,B_N$ とする。
- これを、桁ごとに足し合わせる。$10$ 以上の値が出てきても、ひとまず無視して、数列として扱うことにする。この数列を（上の桁から順に見て） $S_1,S_2,\ldots,S_d$ と置く（$d$ は $B$ の最大桁数）。
- 数列 $S'$ を、$S'=(S_1 \bmod (K+1), S_2 \bmod (K+1), \ldots, S_d \bmod (K+1))$ と定義する（$a \bmod b$ は $a$ を $b$ で割ったあまり）。
- $S'=(0,0,\ldots,0)$ であれば、後手必勝。それ以外は、先手必勝。
以下、これを示すことを目標とします。ここからがお気持ちパートです。以下では、$S'=(0,0,\ldots,0)$ となるような盤面を「特別な盤面」と呼ぶことにします。
$\mathrm{Nim}_K$ の勝敗判定法の証明
ちょっとした言い換え
めんどくさいので、証明することをすり替えます。示したいことは、以下の二つに分けられます：
- 特別な盤面に対して $1$ 回どのような操作を行っても、特別でない盤面しか作ることができない。
- 特別でない盤面に $1$ 回適切に操作を行えば、必ず特別な盤面を作ることができる。
また、操作は各山について分離させて考えるものとします。つまり最終的に、示したいことはこう書けます：
- 特別な盤面の山を再び特別な盤面にするには、必ず $K+1$ 個以上の山の石を取り除く必要がある。
- 特別でない盤面の $K$ 個以下の山の石を適切に取り除くことで、特別な盤面にできる。
以下、これを示すことを目標とします。
本題
「特別でない盤面の $K$ 個以下の山の石を適切に取り除くことで、特別な盤面にできる」ことの証明
先ほど用意した $S'$ について、$S'=(S'_1,S'_2,\ldots,S'_d)$ とします。
出来るだけ少ない数の山の石を取ることで、$S'$ を特別にしたいです。
前から順に、$S'_i$ の値を $0$ にすることを目指します。
$S'_i \neq 0$ なる最小の $i$ を取ります。当然のことですが、$A_1,A_2,\ldots,A_N$ の内には、上から $i$ 番目の bit が立っている数が少なくとも $S'_i$ 個あります。
これら $S'_i$ 個を選んで、とりあえずそれぞれ石の個数を「上から $i$ 番目の bit が立たない最小の数」 に置き換えてみましょう（これは暫定的なもので、あとからさらに数を減らすこともあります）。
すると、以下のようなことが分かります：
- 選んだ $S'_i$ 個の山の石の数について、「$i+1$ 番目以降の bit を立てるかどうか」がこれ以降自由に決められる。
そして、ここで $S'$ を再計算すると、$S'_i \neq 0$ なる最小の $i$ の値は増加します。
これに、今行ったのと同様の操作を行うことを考えましょう。
$S'_i \neq 0$ なる最小の $i$ を取って、$S'_i = 0$ とすることを目指します。
ここで、先ほどと異なる、非常に重要なポイントがあります。
「既に選んで少しでも石取った山については、今見ている桁を自由に $1$ 減らせる」ということです。
ですから、既に石の数を変更した山を優先しながら今見ている桁の bit を減らすことで、「節約」をすることができます。
この事実から、今までに石を取ったことのある山の数を $x$ として、ある $i$ について $S'_i$ を $0$ にしたとき、$x = \max(x,S'_i)$ のように更新できることが分かります。
よって、結局、すべての $S'_i$ を $0$ とするために必要な「石を取る山の数」は、最小で $\max(S')$ 個に抑えられることが分かりました。
定義より、$S'_i \leq K \ (1 \leq i \leq d)$ ですから、特別でない盤面は、$K$ 回以下の操作で特別な盤面に作り替えられることが示せました。
「特別な盤面の山を再び特別な盤面にするには、必ず $K+1$ 個以上の山の石を取り除く必要がある」の証明
正直さっきと同じなのであまり説明は必要ないと思います。
一言で言うなら、「どこかしらの桁は $\bmod (K+1)$ で一周しなきゃいけないので、最低でも $K+1$ 回操作が必要だよね」的な感じです。
おわり
この判定法思いついた人のエスパー力すげーな、って思いました
$2$ 進数を桁ごとに足して $\bmod (K+1)$ をとるとか直感的に嫌じゃないですか？
おまけ
うにむく
ゲーム問題の Um_nik、Unim_k
— NatsubiSogan (@NatsubiSogan) 2022年3月30日
Um_nik さん、普通にコンテストに出てますが身の安全は確保できたのでしょうか
