ゲーム理論の問題

難易度 2教科書の演習問題レベル証明問題大学数学ゲーム理論

石の山が 1 つあり、2 人のプレイヤーが交互に、山から石を $1$ 個、 $2$ 個、 $5$ 個のいずれかの個数だけ取り除く（山にある石より多くは取れない）。石の個数が $n$ （ $n$ は $0$ 以上の整数）の局面のグランディ数 $g (n)$ を
$g (n) = mex {g (n - k) ∣ k \in {1, 2, 5}, k \leq n}$
で定める。ここで、 $0$ 以上の整数からなる有限集合 $A$ に対し、 $mex A$ は $A$ に属さない最小の $0$ 以上の整数を表す（特に $mex \emptyset = 0$ ）。

すべての $0$ 以上の整数 $n$ について、 $g (n)$ は $n$ を $3$ で割った余りに等しいことを証明せよ。

この問題で使うもの

グランディ数と mex（説明と入口の問題）

ヒント

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

ヒント 1

$n$ についての強い数学的帰納法を使いましょう。 $n$ より小さいすべての $m$ で $g (m) = m mod 3$ が成り立つと仮定し、 $A_{n}$ に何が入っているかを調べます。

ヒント 2

取れる個数 $1, 2, 5$ を $3$ で割った余りは $1, 2, 2$ で、どれも $0$ ではありません。したがって $n - k$ の余りは $n$ の余りと必ず異なります。

ヒント 3

$r = n mod 3$ とすると、 $r$ 自身は $A_{n}$ に入りません。あとは $r$ 未満の値 $0, \dots, r - 1$ が $A_{n}$ にすべて入ることを、 $r = 0, 1, 2$ で場合分けして確かめます（そのとき、 $k = 1, 2$ の手が実際に可能かどうかに注意します）。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

強い数学的帰納法を用いることと、何を仮定して何を示すか（ $m < n$ で $g (m) = m mod 3$ を仮定し $g (n)$ を求める）を明記し、 $n - k < n$ だから仮定が使えることを述べている（2 点）
$1, 2, 5$ がどれも $3$ の倍数でないことから、 $g (n - k) \neq = n mod 3$ 、すなわち $n mod 3$ が選択肢の値の集合に入らないことを示している（3 点）
$n mod 3 = 1, 2$ のとき、 $k = 1$ （と $k = 2$ ）の手が実際に可能であることを確認し、 $0$ （と $1$ ）が選択肢の値の集合に入ることを示している（3 点）
mex の定義から $g (n) = n mod 3$ を結論し、 $n = 0$ の場合も含めて帰納法を完結させている（2 点）

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

模範解答を読む

$n$ を $3$ で割った余りを $r (n) \in {0, 1, 2}$ と書く。すべての $0$ 以上の整数 $n$ について $g (n) = r (n)$ であることを、 $n$ についての強い数学的帰納法（累積帰納法）で示す。すなわち、 $n \geq 0$ を固定し、 $0 \leq m < n$ をみたすすべての $m$ について $g (m) = r (m)$ が成り立つと仮定して、 $g (n) = r (n)$ を示す（ $n = 0$ のときは仮定は空であり、以下の議論はそのまま当てはまる）。

$A_{n} = {g (n - k) ∣ k \in {1, 2, 5}, k \leq n}$ とおく。 $k \leq n$ のとき $0 \leq n - k < n$ なので、帰納法の仮定より $g (n - k) = r (n - k)$ である。

ステップ 1: $A_{n}$ は $r (n)$ を含まない。
$k \in {1, 2, 5}$ はいずれも $3$ の倍数でないので、 $n - k$ と $n$ は $3$ を法として合同でなく、 $r (n - k) \neq = r (n)$ である。よって $r (n) \in / A_{n}$ 。

ステップ 2: $A_{n}$ は $r (n)$ 未満の $0$ 以上の整数をすべて含む。 $r = r (n)$ で場合分けする。
- $r = 0$ のとき: $0$ 未満の $0$ 以上の整数はないので、示すことはない。
- $r = 1$ のとき: $0$ が $A_{n}$ に入ることを示せばよい。 $r (n) = 1$ より $n \geq 1$ なので $k = 1$ の手が可能で、 $n - 1 \equiv 0 (mod 3)$ より $g (n - 1) = r (n - 1) = 0 \in A_{n}$ 。
- $r = 2$ のとき: $0, 1$ が $A_{n}$ に入ることを示せばよい。 $r (n) = 2$ より $n \geq 2$ なので $k = 1, 2$ の手が可能で、 $n - 1 \equiv 1$ 、 $n - 2 \equiv 0 (mod 3)$ より $g (n - 1) = 1$ 、 $g (n - 2) = 0$ がともに $A_{n}$ に入る。

ステップ 3: 結論。 ステップ 2 より $0, 1, \dots, r (n) - 1$ はすべて $A_{n}$ に属し、ステップ 1 より $r (n)$ は $A_{n}$ に属さない。したがって $A_{n}$ に属さない最小の $0$ 以上の整数は $r (n)$ であり、 $g (n) = mex A_{n} = r (n)$ である。

（なお $n = 0$ のとき $A_{0} = \emptyset$ で $g (0) = 0 = r (0)$ となり、上の議論の $r = 0$ の場合と一致している。）

以上より、強い数学的帰納法によって、すべての $0$ 以上の整数 $n$ について $g (n)$ は $n$ を $3$ で割った余りに等しい。

この問題の確認

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

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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