石の山がいくつかある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それをどちらも 個以上の石を含む 2 つの山に分ける（2 つの山の個数は等しくてもよい）。
操作できなくなったプレイヤーが負けである。たとえば 個の山は「 個と 個」または「 個と 個」に分けられる。 個、 個、 個の山は分けられない。
石が 個の山 1 つだけの局面のグランディ数を求めよ。
山を分けるゲームのグランディ数
1 つの山を 2 つの山に分ける操作のゲームで、分けた後の 2 山のグランディ数のニム和をすべて挙げ、その mex として小さい山から順にグランディ数の表を作れる（例: 個数の異なる 2 山に分けるゲーム）
前提
- グランディ数と mex （大学数学 ゲーム理論）
- ニムとニム和 （大学数学 ゲーム理論）
この技能までの道筋（9 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- グランディ数と mex （大学数学 ゲーム理論）
- 分数のたし算・ひき算 （算数 計算と数のきまり）
- 小数の四則計算 （算数 計算と数のきまり）
- 正負の数の加法・減法 （中学数学 数と式）
- 分数のかけ算・わり算 （算数 計算と数のきまり）
- 四則の混じった計算の順序 （算数 計算と数のきまり）
- 正負の数の乗除・累乗と四則混合 （中学数学 数と式）
- n 進法 （数学A 整数の性質）
- ニムとニム和 （大学数学 ゲーム理論）
説明
石の山から石を「取る」のではなく、山を「2 つに分ける」ことで進むゲームでも、グランディ数を使えば勝敗を判定できます。ここでは代表例として、1 つの山を個数の異なる 2 つの山に分ける「グランディのゲーム」を扱います。分けた後の 2 山のグランディ数のニム和をすべて並べ、その mex をとります。こうして小さい山から順にグランディ数の表を作れば、どの局面が先手必勝かがわかり、勝つための分け方も求められます。
なぜそうしてよいのか
山を分けると、局面は 1 つの山ではなく、いくつかの山の集まりになります。その後の各手番では、どれか 1 つの山を選んで分けます。つまり各山は互いに影響しない別々のゲームで、プレイヤーは毎回そのうち 1 つだけで手を指します。これは、ニムで「どれか 1 つの山から石を取る」のと同じ構造です。そのため、山の集まり全体のグランディ数は、各山のグランディ数のニム和 になります（スプラーグ・グランディの定理）。
直観的な理由を説明します。グランディ数が の局面からは、mex の定義により、 のどの値の局面にも 1 手で移れます。一方、値がちょうど の局面には移れません。これは「石が 個あるニムの山から、好きな個数を取れる」のと同じ働きです。値が より大きい の局面に移れる場合もあります。しかし なので、そこからは 1 手で値 の局面に戻せます。そのため、相手はこうした手を打ち消せます。こうして各山は、石が 個と 個のニムの山として振る舞います。そして、その 2 山のニムのグランディ数がニム和 です。
したがって、山 から 1 手で移れる局面のグランディ数は、分け方 ごとの です。これらを集めた集合の mex が になります。右辺には より小さい山のグランディ数しか出てこないので、 の順に表を埋めていけます。
手順
分け方を整理する。個数の異なる 2 山に分けるゲームでは、山 を に分ける（ は を満たす整数）。 の等分は禁止なので含めない。
分けられない山のグランディ数を とする。移れる局面がないので、空集合の mex をとって になる。 は分けられず、 も が等分なので分けられない。よって 。
の順に進める。各 について、すべての分け方 で を表から計算し、集合にまとめる。
その集合の mex（集合に含まれない最小の 0 以上の整数）を として表に書き込む。
複数の山からなる局面では、各山のグランディ数のニム和を局面全体の値とする。値が なら後手必勝、 でなければ先手必勝である。先手必勝のときは、ニム和を にする分け方が勝つ手になる。
例題
2 人が交互に手を指すゲームを考える。1 手では、どれか 1 つの山を選び、個数の異なる 2 つの空でない山に分ける。手を指せなくなった人が負けである。石 9 個の山 1 つのグランディ数 を求めよ。
例題の解答
【手順 1・2】山 は （）に分けられる。 は分けられないので、。
【手順 3・4】小さい順に表を作る。
・: の値は 。集合 の mex より 。
・: の値は 。 は等分なので除く。集合 の mex より 。
・: の値は 、 の値は 。集合 の mex より 。
・: の値は 、 の値は 。 は除く。集合 の mex より 。
・: の値は 、 の値は 、 の値は 。集合 の mex より 。
・: の値は 、 の値は 、 の値は 。 は除く。集合 の mex より 。
・: の値は 、 の値は 、 の値は 、 の値は 。集合は で、mex は 。
よって 。
【手順 5】値が でないので、9 個の山 1 つから始めると先手必勝である。例えば に分けると局面の値が になり、これが勝つ手になる。
答え:
よくある誤り
等分の分け方まで数えてしまう誤り。例えば で （値 ）を入れると集合が となり、 と誤る。正しくは は禁止なので、集合は で 。
2 山のグランディ数を普通の和で合わせてしまう誤り。表を続けると となる。 を求めるとき、 の値を としてしまうと、集合が となり、 と誤る。正しくはニム和で である。分け方ごとの値は が 、 が 、 が 、 が 、 が 、 が である。よって集合は で、。
分けられない山（）のグランディ数を決めずに飛ばしたり、 としたりする誤り。正しくは、移れる局面がないので空集合の mex をとり、。
mex を「集合の最大値 」と取り違える誤り。例えば の mex を としてしまう。正しくは、含まれない最小の 0 以上の整数なので 。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
石の山がいくつかある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それをどちらも 個以上の石からなる 2 つの山に分ける（2 つの山の個数は等しくてもよい）。たとえば 個の山は「 個と 個」または「 個と 個」に分けられる。
操作ができなくなったプレイヤーの負けとする。石が 個の山 1 つだけからなる局面のグランディ数を求めよ。
いくつかの石の山がある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それを 2 つの山に分ける。ただし、分けた後の 2 つの山は、どちらも石が 個以上でなければならない（たとえば 個の山は 個と 個、または 個と 個に分けられる）。
操作ができなくなったプレイヤーが負けとする。石が 個の山 1 つだけからなる局面のグランディ数を とする（ は正の整数）。 を求めよ。
この技能を使う問題
いくつかの石の山がある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それを石の個数が異なる 2 つの空でない山に分ける（たとえば 個の山は 個と 個、 個と 個、 個と 個のいずれかに分けられる。 個の山を 個と 個に分けることはできない）。
操作ができなくなったプレイヤーの負けとする（石が 個または 個の山はもう分けられない）。
最初に石が 個、 個、 個の つの山があり、先手から始める。先手の最初の操作のうち、その後の後手の操作によらず先手が必ず勝てるようにする操作（勝ちにつながる手）は何通りあるか。ただし、操作は「どの山を選ぶか」と「どの 2 つの個数に分けるか」の組で区別し、分けてできる 2 つの山の順序は区別しない。
横一列に並んだマス目からなる細長い盤が 枚あり、マスの個数はそれぞれ 個、 個、 個である。はじめはすべてのマスが空いている。2 人のプレイヤーが交互に、どれか 枚の盤を選び、その盤の隣り合う つの空きマスにドミノを 枚置く（置いたドミノは以後動かさない。ドミノは盤をまたいで置けない）。自分の手番でドミノを置けなくなったプレイヤーの負けとする。
この初期局面で先手が必勝であることが知られている。先手の最初の手のうち、その手を打った後も先手が必勝であり続ける手（必勝手）は何通りあるか。ただし、ドミノが覆う マスの組が異なる置き方は、異なる手として数える。