1・3・4個取りと減算ゲーム

減算ゲームでは、一つの山から取れる個数を集合で指定します。ここでは毎手1、3、4個のどれかを取り、最後を取った側が勝つ規則を扱います。小さい局面からの計算と、見つかった周期の証明を組み合わせて必勝法を得られます。

連続しない選択肢に注意する

取れる個数の集合をS＝{1,3,4}とします。2個取る手は許されず、残りが少なければ3個や4個も取れません。例えば残り2個なら1個だけ取るしかなく、相手が最後の1個を取って勝ちます。最大4個だから5の倍数を目指せばよい、という考えは成り立ちません。最大値に加え、途中のどの数を選べるかが局面の構造を変えます。

小さい数から勝敗表を作る

0個は負けです。1個は0へ移れるので勝ち、2個は1にしか移れないので負けです。3個と4個は全部取れるため勝ち、5個は3個取って2へ、6個は4個取って2へ移れるため勝ちです。7個の移動先は6、4、3で全て勝ちなので負けになります。この手順は、それ以前の結果を保存して再利用する動的計画法として計算できます。

負けの数は7で割って0か2

この規則のP局面は、7で割った余りが0または2になる数です。0、2、7、9、14、16などが該当します。例えば17個は3個取って14へ、18個は4個取って14へ移れます。表を眺めて周期を推測することは出発点ですが、最初の数例が一致しただけでは無限に続く保証にはなりません。次の余りの確認で、すべての数をまとめて扱えます。

七つの余りで証明する

余り0から1、3、4を引くと余り6、4、3、余り2から引くと1、6、5となり、P候補同士へ移れません。他の余りでは、1から1、3から1、4から4、5から3、6から4を引けば、余り0か2へ移れます。小さい数でも示した手が合法かを確認すると、P候補の外から必ずP候補へ入れます。終局0も候補に含むので、帰納的に判定が確定します。

規則を変えたら再計算する

別の集合を選ぶと、負けの数も周期も変わります。有限個の正の整数だけを引くなら、ある地点の判定は直前の有限範囲の勝敗に依存します。同じ判定状態が再び現れれば、その後の結果も繰り返します。ただし初めから周期が始まるとは限りません。また、平方数をいくつでも引けるなど無限の選択集合では、同じ有限状態の議論をそのまま使えません。

関連項目