Grundy数（Nim数, Nimber）の理論

■「競プロでのゲーム問題って得意？」 ●「ゲーム問題ですか。ものによりますけど、Grundy 数で解ける問題は得意ですね。先輩は得意ですか？」 ■「その Grundy 数がよくわからないんだよね。最後から逆にたどると解ける問題とかは分かるんだけど、Grundy 数の何が嬉しいのかよくわからない」 ●「じゃあ今日はGrundy数のお話をしましょうか」 Grundy数を扱えるゲーム ●「Grundy 数は、ゲームの局面に非負整数を割り当てて必勝法や勝敗判定を行うというものです」 ■「ゲームなら何でも Grundy 数が使えるの？」 ●「そういうわけではないんですが、競プロで出てくるゲームなら使えるものは多いですね」 ■「何か必要条件があるってこと？」 ●「はい。公平ゲーム（不偏ゲーム）と呼ばれるゲームである必要があります。それにはこんな条件が必要です」 2人のプレーヤーは、terminal p