変種石取りゲームの必勝法

「負け状態」＝「全ての山について石の個数のXORをとると０」
証明は省きます。（「Nim」とかで調べればたくさん出てくると思うので）

「負け状態」＝「石の個数がもっとも多い山の個数が偶数個」
（「石の個数がもっとも多い山にある石の個数が偶数個」ではないことに注意してください）
（証明）
1.「負け状態」からの遷移について
石を一つ以上取らなくてはならないことから、石がもっとも多い山の個数は必ず1減少し、奇数になります。
2.「勝ち状態」からの遷移について
石の数がもっとも多い山の個数が３個以上だった場合、ある山から石を1つだけ取れば良いです。
山の個数が１個だった場合、石の取り方を工夫することで、もっとも多い山の個数を必ず偶数にすることができます。

「負け状態」＝「石の個数がもっとも多い山にある石の個数をnとしたとき、nが偶数で、かつ、n-1個の石があるような山も存在する」
（証明）
1.「負け状態」からの遷移について
石を2個以上取らなくてはならないことから、もっとも多い山にある石の個数はn-1となり、これは奇数であるため勝ち状態への遷移となります。
2.「勝ち状態」からの遷移について
n以外で最大のものが奇数であったなら、その値をkとして、n個の石の山から取ってk+1個にすれば良いです。
n以外で最大のものが偶数であったなら、その値をkとして、k-1個の石の山が存在するように石を取れば良いです。

「負け状態」＝「石の数が１個ではない山が存在し、矢印が指している山にある石の個数が１個で、石が１個しかない山の個数が奇数個」もしくは「全ての山にある石の数が１個で、山の数が偶数個」
（証明）
1.「負け状態」からの遷移について
必ず１個しかない山の個数が１減少するので、石が１個しかない山の数の偶奇が反転します。
2.「勝ち状態」からの遷移について
全ての山にある石の個数が１個で、山の数が奇数個のとき、山の数が偶数個になります。
矢印が指している山にある石の個数が１個では無い場合、
１個の山が偶数個で、その山以外に１個ではない山が存在する場合、その山にある石が１個になるように石を取れば良いです。
１個の山が偶数個で、その山以外に１個ではない山が存在しない場合、石を全て取れば良いです。
１個の山が奇数個で、その山以外に１個ではない山が存在する場合、石を全て取り、１個の山を指すように矢印を移動させると良いです。
１個の山が奇数個で、その山以外に１個ではない山が存在しない場合、その山にある石が１個になるように石を取れば良いです。
矢印が指している山にある石の個数が１個の場合、
全てが１個の山で、山の数が奇数個の場合、山の数が偶数個になります。
１個ではない山があって、１個の山の数が偶数個の場合、１個の山の数が奇数個になります。

「負け状態」＝「山の個数が偶数個で、かつ、矢印の指している山にある石の個数が、全ての山の中で最も少ない」
（証明）
1.「負け状態」からの遷移について
石を残した場合、矢印の指す山は最小の山ではなくなります。
石を全て取る場合、山の個数が偶数個ではなくなります。
2.「勝ち状態」からの遷移について
山の個数が偶数個の場合、その山から石を１つ以上とって、最小の山に矢印を動かせば良いです。
山の個数が奇数個の場合、その山の石を全て取って、最小の山に矢印を動かせば良いです。

「負け状態」＝「全ての山にある石の個数を２で割って切り捨てて、その上で3-1に帰着させた時の負け状態と同じ」
（証明）
まず、取るべき石の個数が偶数・奇数と入れ替えさせるコインの存在が厄介です。
そこで今回は、取るべき石の個数は「常に偶数である」としてしまいましょう。
そうすると、山の個数を２で割って切り捨てることで、通常のNimに帰着させることができます。
しかし、コインが裏を向いている時は、石を取る個数は奇数になってしまう事実は変わりません。どうすれば良いのでしょうか？

実は、コインの表裏が勝敗に関係しないことがわかります。
まず、コインがずっと表を向いていると仮定した場合には、勝敗を決めることができます。このときの仮定の下で勝利が約束された側を「勝者」、そうでない側を「敗者」と呼ぶことにしましょう。
このとき、勝者は当然ですがコインを表にした状態で敗者に渡すのが最適です。問題は、敗者がコインを裏にした状態で自分の手番に回してきた場合について考えます。
当初の予定（表で回ってくるとした仮定の下）で、「m個ある石の個数を2k、あるいは2k+1にしよう」と考えていたとします。2kにしようと思っていた場合、2k+1個にすることができます。2k+1にしようと思っていた場合、2kにすることができます。よって、勝者の立場は揺らがないことがわかります。
（よりformalに説明するには、grundy数という概念を導入するとわかりやすいです。コインが表から裏になることで、各山のgrundy数は増加こそすれ減少はしないということがわかります。）