石取りゲーム

AさんとBさんが次のゲームをします.

• 5個のコインの山があって, それぞれの山には5,8,6,10,7枚のコインがある.
• AさんとBさんが交互に”一つの山”を選び, そこからコインを取ります. ただし一度にとるコインの枚数は1,3,4枚のいずれかと等しくないといけない.
• 最後にコインを取った方が勝ち.
• 両者とも最善を尽くして戦う.

最初の手番がAさんであるとき, どちらが勝つでしょうか?

コメント

2023年の授業で出した. 蟻本にそのまま同じ問題が載っている.

実はこの問題が数学的にどこまで解けているか知りたくて学問の扉でもこの問題を出した. 調べてみると, “Sprague–Grundy theorem”という定理に行き着いた. もっと調べると, SpragueさんがTohoku Journalに論文を出していたみたいである. GrothendieckにしかりTohoku Journalは面白い論文が多いなあと思った.