隣の山に石を渡していく Nim (staircase nim)

ふと TL に出してみた。絶対既出だと思ったから流したけど、どこかにあるかな...？？？

アイディア自体は

• SRM 309 DIV1 Hard StoneGameStrategist
• POJ 1704 Georgia and Bob (蟻本の例題)

と同じものだったりする。むしろ問題に対してある種の同型変換を施すと、3 問ともまったく同じ問題であることが示せたりする！！！！！

あと、staircase nim という名前があるらしい。

問題概要

個の石の山が左から順に一列に並んでおり、それぞれ 個の石を含んでいる。右端の山の右横には石置き場があり、最終的に全ての石を石置き場に移動させることを目指す (先にその状態にした方が勝ち)。

先手と後手は交互に空でない石の山を一つ選び、そこから1個以上の石を取ってそれを右隣の山に移動させる。右端の山から石を取った場合は、それを石置き場に移動させる。お互いが最善を尽くしたとき、先手後手どちらが勝つでしょうか？

制約

• 
• 

解法

まず、(5, 0, 6, 0, 100, 0, 4, 0, 7, 0) みたいな「右から奇数番目がすべて 0」という盤面は既に必敗盤面になっていることに注意する。何故なら例えばこの盤面の石 100 個の山から 9 個とって

(5, 0, 6, 0, 100, 0, 4, 0, 7, 0) -> (5, 0, 6, 0, 91, 9, 4, 0, 7, 0)

としたとき、相手は

(5, 0, 6, 0, 91, 9, 4, 0, 7, 0) -> (5, 0, 6, 0, 91, 0, 13, 0, 7, 0)

としてしまえばよい。こうして同じ形に持ち込むことができる。このことから、「右から奇数番目の個数」はどうでもよくて、

• についての Nim なんじゃないか...？

という着想が浮かぶ。そのことを示してみる。

証明

以下の 3 つを示せば良い:

---

1. ^ ^ ^ のとき、次にどのような手を打っても、その条件が崩れる
2. ^ ^ ^ のとき、上手く手を打つことで ^ ^ ^ の状態にできる
3. 操作は有限回数で必ず終了し、終局状態は ^ ^ ^ の状態である

---

まず、右から奇数番目の山のみに着目してみたとき、

• 山を 1 つ選んで石の個数を任意に減らせる (右隣の山、もしくは石置き場に石を任意個数移す操作に対応)

という通常の Nim に対し、

• その山の石の個数を少しだけ増やすこともできる (左隣の山から石が持ち込まれることに対応)

という操作もつけ加わったものだと思うことができる。実はこの程度の操作変更では Nim はビクともしない！！！

1. について

石の個数が増える操作が加わっても、操作を行うと必ず

• ^ ^ ^

が崩れることは自明である。簡単のため、 ^ ^ = 0 が成り立っているときに を に変更するものとする。このときまず XOR の性質から

^ =

が成り立っているため、

^ ^ = ^

となる。 でない限り、 ^ ^ = とはならないことがわかる。

2. について

これについては「石の個数が増える」という操作の追加は何も意味を持たない。従来の「石の個数を任意に減らせる」という操作だけで

• ^ ^ ^ の状態から ^ ^ ^ の状態にすること

が実現できるのは、通常の Nim と同じである。

3. について

通常の Nim に「石の個数を増やす」操作を追加したものも実質 Nim と同じだと言ったが、厳密にはダメ。何故ならその場合、ゲームを無限に続けることができてしまうから。。。

でも、この問題のゲームの場合は、

• 

の値が常に単調減少なので有限停止性が保証できる。そして終局時の各山の石の個数は であり、これは ^ ^ ^ の状態である。

まとめ

以上より、

• ^ ^ ^ ならば後手必勝
• ^ ^ ^ ならば先手必勝

であることが導かれた。