ゲーム理論の問題
難易度 1教科書の例題レベル大学数学 ゲーム理論
石が つの山に積まれている。2 人のプレイヤーが交互に、この山から石をちょうど 個または 個取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする。石が 個（ は 以上の整数）の山のグランディ数を とする。ただし、集合 （ 以上の整数からなる有限集合）に対して を「 に含まれない最小の 以上の整数」とし、（移れる局面がないときは ）と定める。 を求めよ。
この問題で使うもの
- グランディ数と mex（説明と入口の問題）
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
グランディ数と mex の技能を使う。 から順に、1 手で移れる局面のグランディ数の集合の mex を計算して表を作る。
ヒント 2
個の山から移れるのは 個と 個の山なので、 となる。表の値がくり返し始めるところを探す。
ヒント 3
は となり、周期 でくり返す。 を で割った余りを考える。
答えと解説
答えを見る
結果を記録する（このブラウザにだけ保存されます）:
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
石が 個の山から 1 手で移れるのは、 なら 個、 なら 個の山である。したがって
（ただし存在しない局面は除く）で、小さい から順に計算する。
- （取れない）
- （ 個では 個も 個も取れない）
表にすると
では は直前の値 だけで決まる。 なので、ここから先は と同じ計算がくり返される。よって がすべての で成り立ち、グランディ数は周期 で をくり返す。
なので
別解
とする。ただし、 や の項は、その手が存在しないので集合に入れない。
、（動けない）。
。
。
。
。
。
。
。
。
。
よって 、 などが成り立ち、 は と同じ値になる。漸化式は直前の 3 項だけで決まるので、周期 5 で を繰り返す。
なので 。