ゲーム理論の問題
石の山がいくつかある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それをどちらも 個以上の石を含む 2 つの山に分ける（2 つの山の個数は等しくてもよい）。
操作できなくなったプレイヤーが負けである。たとえば 個の山は「 個と 個」または「 個と 個」に分けられる。 個、 個、 個の山は分けられない。
石が 個の山 1 つだけの局面のグランディ数を求めよ。
この問題で使うもの
- 山を分けるゲームのグランディ数（説明と入口の問題）
この問題を解けるようになるまで（10 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
「山を分けるゲームのグランディ数」の技能を使います。2 つに分けた後の局面のグランディ数は、2 つの山のグランディ数のニム和です。その mex をとって、小さい山から順に表を作りましょう。
ヒント 2
です。そのため、 から までが必要になります。
ヒント 3
、 です。 は と の分け方から求めます。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
個の山のグランディ数を とする。山を 個と 個に分けた後の局面は 2 つの山の和なので、そのグランディ数は （ニム和）である。 は、1 手で移れる局面のグランディ数の集合の mex である。小さい山から順に求める。
： 個以上ずつの 2 山には分けられないので、移れる局面がない。よって 。
：分け方は だけである。 なので、。
：分け方は だけである。 なので、。
：分け方は と である。
- ：
- ：
よって 。
：分け方は と である。
- ：
- ：
よって 。
：分け方は 、、 である。
- ：
- ：
- ：
移れる局面のグランディ数の集合は である。したがって
となる。
別解
山の大きさ のグランディ数を とおく。 個の山を、どちらも 個以上の山 （）に分けると、グランディ数は になる。 はこれらの値全体の mex である。
- （分けられない）。
- ： のみで 。よって 。
- ： のみで 。よって 。
- ： で 、 で 。よって 。
- ： で 、 で 。よって 。
- ： で 、 で 、 で 。よって 。
答えは である。