ゲーム理論の問題

難易度 1教科書の例題レベル大学数学ゲーム理論

石の山が $4$ つあり、石の個数はそれぞれ $4$ 個、 $6$ 個、 $8$ 個、 $9$ 個である。2 人のプレイヤーが交互に、どれか 1 つの山を選び、その山から石をちょうど $2$ 個または $3$ 個取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする。

この局面から先手が打てる手のうち、移った先の局面のグランディ数が $0$ になる手（勝ちにつながる手）は何通りあるか求めよ。ただし、手は「どの山から何個取るか」の組で区別する。

この問題で使うもの

スプレイグ・グランディの定理と勝ちにつながる手（説明と入口の問題）

この問題を解けるようになるまで（10 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

スプレイグ・グランディの定理を使う。まず 1 つの山のグランディ数を mex で求め、局面全体のグランディ数を各山のグランディ数のニム和として求める。

ヒント 2

石が $n$ 個の山のグランディ数は $g (n) = mex {g (n - 2), g (n - 3)}$ （取れる分だけ）である。全体のニム和を $s$ とすると、グランディ数 $g_{i}$ の山を $g_{i} \oplus s$ の山に変える手が勝ちにつながる手になる。

ヒント 3

$g (0), g (1), \dots$ は $0, 0, 1, 1, 2, 0, 0, 1, 1, 2$ となり、 $g (4) = 2, g (6) = 0, g (8) = 1, g (9) = 2$ で、全体のニム和は $1$ である。あとは各山について、 $2$ 個または $3$ 個取った先のグランディ数が $g_{i} \oplus 1$ になるかを調べればよい。

答えと解説

答えを見る

3

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順 1：1 つの山のグランディ数を求める。

石が $n$ 個の山のグランディ数を $g (n)$ とする。 $n$ 個の山からは $n - 2$ 個または $n - 3$ 個の山へ移れる（石が足りない手は打てない）。小さい順に mex を計算すると

$g (0) = 0$ 、 $g (1) = 0$ （動かせない）
$g (2) = mex {g (0)} = mex {0} = 1$
$g (3) = mex {g (1), g (0)} = mex {0} = 1$
$g (4) = mex {g (2), g (1)} = mex {1, 0} = 2$
$g (5) = mex {g (3), g (2)} = mex {1} = 0$
$g (6) = mex {g (4), g (3)} = mex {2, 1} = 0$
$g (7) = mex {g (5), g (4)} = mex {0, 2} = 1$
$g (8) = mex {g (6), g (5)} = mex {0} = 1$
$g (9) = mex {g (7), g (6)} = mex {1, 0} = 2$

よって 4 つの山のグランディ数は $g (4) = 2, g (6) = 0, g (8) = 1, g (9) = 2$ である。

手順 2：スプレイグ・グランディの定理で局面全体のグランディ数を求める。

局面全体のグランディ数は各山のグランディ数のニム和である。
$2 \oplus 0 \oplus 1 \oplus 2 = (2 \oplus 2) \oplus 0 \oplus 1 = 1$
$0$ でないので先手必勝である。

手順 3：グランディ数 $0$ の局面へ移る手を数える。

ある山のグランディ数を $g_{i}$ から $g_{i}^{'}$ に変えたとき、全体は $1 \oplus g_{i} \oplus g_{i}^{'}$ になる。これが $0$ になるのは $g_{i}^{'} = g_{i} \oplus 1$ のときである。各山で調べる。

$4$ 個の山（ $g = 2$ ）：目標は $2 \oplus 1 = 3$ 。移れる先は $2$ 個（ $g = 1$ ）、 $1$ 個（ $g = 0$ ）で、 $3$ にはならない。 $0$ 通り。
$6$ 個の山（ $g = 0$ ）：目標は $0 \oplus 1 = 1$ 。移れる先は $4$ 個（ $g = 2$ ）、 $3$ 個（ $g = 1$ ）。 $3$ 個取って $3$ 個にする手が条件を満たす。 $1$ 通り。
$8$ 個の山（ $g = 1$ ）：目標は $1 \oplus 1 = 0$ 。移れる先は $6$ 個（ $g = 0$ ）、 $5$ 個（ $g = 0$ ）で、どちらも条件を満たす。 $2$ 通り。
$9$ 個の山（ $g = 2$ ）：目標は $3$ 。移れる先は $7$ 個（ $g = 1$ ）、 $6$ 個（ $g = 0$ ）で、 $3$ にはならない。 $0$ 通り。

確認：たとえば $8$ 個の山から $2$ 個取ると $2 \oplus 0 \oplus 0 \oplus 2 = 0$ となる。

以上より、勝ちにつながる手は $0 + 1 + 2 + 0 = 3$ 通りである。

別解

2 または 3 個取る引き算ゲームの 1 つの山のグランディ数 $g (n)$ を求める。 $g (0) = 0, g (1) = 0$ 。 $g (n) = mex {g (n - 2), g (n - 3)}$ （ $n - 2, n - 3 \geq 0$ のものだけ）より、
$g (2) = mex {0} = 1$ 、 $g (3) = mex {0, 0} = 1$ 、 $g (4) = mex {1, 0} = 2$ 、 $g (5) = mex {1, 1} = 0$ 、 $g (6) = mex {2, 1} = 0$ 、 $g (7) = mex {0, 2} = 1$ 、 $g (8) = mex {0, 0} = 1$ 、 $g (9) = mex {1, 0} = 2$ 。

山 $4, 6, 8, 9$ のグランディ数は $2, 0, 1, 2$ で、全体は $2 \oplus 0 \oplus 1 \oplus 2 = 1 \neq = 0$ 。移った先の全体を $0$ にするには、ある山のグランディ数を $g \oplus 1$ にすればよい。

4 の山（ $g = 2$ 、目標 $3$ ）：移り先は 2（ $g = 1$ ）、1（ $g = 0$ ）で、目標の $3$ にならない。0 通り。
6 の山（ $g = 0$ 、目標 $1$ ）：3 個取って 3（ $g = 1$ ）なら可、2 個取って 4（ $g = 2$ ）は不可。1 通り。
8 の山（ $g = 1$ 、目標 $0$ ）：2 個取って 6（ $g = 0$ ）、3 個取って 5（ $g = 0$ ）のどちらも可。2 通り。
9 の山（ $g = 2$ 、目標 $3$ ）：移り先は 7（ $g = 1$ ）、6（ $g = 0$ ）で、目標の $3$ にならない。0 通り。

合計 $0 + 1 + 2 + 0 = 3$ 通り。

検算：6→3 の後の局面は 4,3,8,9 で、グランディ数は $2, 1, 1, 2$ なので XOR は $0$ 。8→6 の後は 4,6,6,9 で $2, 0, 0, 2$ なので XOR は $0$ 。8→5 の後は 4,6,5,9 で $2, 0, 0, 2$ なので XOR は $0$ 。いずれも正しい。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる