京都大学理学部特色入試 2017年度第3問解説

🕒 2016/11/27 🔄 2024/09/21

（2016年11月に行われた特色入試の問題です。2017年に行われた特色入試の問題はこちら）

問題編

問題

　A, B の2人が次のゲームを行う。初期状態として、台の上に n 個の石が置いてある。最初に A, 次に B の順で交互に、台から1個以上の石を取り除いていく。ただし一度に取り除く個数は自然数の2乗でなければならない。台の上に石がない状態にした方を勝者として、そこでゲームを終了する。
　このゲームが先手必勝であるとは、A が自分の番で取り除く石の個数を適切に選択していけば、B がいかなる選択を行っても、必ず A が勝利できることとする。同様に、このゲームが後手必勝であるとは、B が自分の番で適切に選択を行っていけば、A がいかなる選択を行っても必ず B が勝利できることとする。
　例えば、 $n=10$ のとき、最初に A が取り除ける石の個数は 1, 4, 9 のいずれかである。

A が1個取り除くならば、残りの石の個数は 9 となる。この状態において B が取り除ける石の個数は 1, 4, 9 のいずれかである。 B が9個取り除くという選択を行うと B が勝利する。

A が9個取り除くならば、残りの石の個数は 1 となる。次に B が1個取り除いて B が勝利する。

A が4個取り除くならば、残りの石の個数は 6 となる。この状態において B が取り除ける石の個数は 1, 4 のいずれかである。 B が4個取り除くという選択を行うと、残りの石の個数は 2 となる。この状態において A が取り除ける石の個数は 1 のみであり、その次に B が1個取り除いて B が勝利する。

したがって、 B が自分の番で取り除く石の個数を適切に選択していけば、必ず B が勝利できるので、 $n=10$ のときのゲームは後手必勝である。
　以下の設問に答えよ。

(1) どの自然数 n に対しても、このゲームは先手必勝または後手必勝のいずれか一方であることを示せ。
(2) $n=456$ のとき、このゲームは先手必勝であることを示せ。
(3) このゲームが後手必勝となる n は無限に多く存在することを示せ。

考え方

(1)は深みにはまると抜け出せません。不思議に思うかもしれませんが、お互いの動きが完全にわかり、確率的な要素のないゲームは、「先手が絶対勝つ」か「後手が絶対勝つ」か「引き分け（勝負がつかない）」しかありません。今のゲームは、引き分けがありえないので、先手必勝か後手必勝しかありません。「存在する」と「任意」の否定を考えればわかるでしょう。

(2)は(1)ができなくても解けます。 B の選択肢を少なくした方が考えやすく、そっちのほうが A が戦いやすいので、まずはたくさん石を取り除くことを考えます。後は場合分けをして考えれば、それほど大変ではありません。

(3)は有限しかないと仮定して矛盾を導きます。(1)よりある自然数から先は先手必勝ばかりになってしまいますが、その中に後手必勝のゲームが作れてしまうことを示しましょう。

解答編

問題

　A, B の2人が次のゲームを行う。初期状態として、台の上に n 個の石が置いてある。最初に A, 次に B の順で交互に、台から1個以上の石を取り除いてていく。ただし一度に取り除く個数は自然数の2乗でなければならない。台の上に石がない状態にした方を勝者として、そこでゲームを終了する。
　このゲームが先手必勝であるとは、A が自分の番で取り除く石の個数を適切に選択していけば、B がいかなる選択を行っても、必ず A が勝利できることとする。同様に、このゲームが後手必勝であるとは、B が自分の番で適切に選択を行っていけば、A がいかなる選択を行っても必ず B が勝利できることとする。
　例えば、 $n=10$ のとき、最初に A が取り除ける石の個数は 1, 4, 9 のいずれかである。

A が1個取り除くならば、残りの石の個数は 9 となる。この状態において B が取り除ける石の個数は 1, 4, 9 のいずれかである。 B が9個取り除くという選択を行うと B が勝利する。

A が9個取り除くならば、残りの石の個数は 1 となる。次に B が1個取り除いて B が勝利する。

A が4個取り除くならば、残りの石の個数は 6 となる。この状態において B が取り除ける石の個数は 1, 4 のいずれかである。 B が4個取り除くという選択を行うと、残りの石の個数は 2 となる。この状態において A が取り除ける石の個数は 1 のみであり、その次に B が1個取り除いて B が勝利する。

したがって、 B が自分の番で取り除く石の個数を適切に選択していけば、必ず B が勝利できるので、 $n=10$ のときのゲームは後手必勝である。
　以下の設問に答えよ。

(1) どの自然数 n に対しても、このゲームは先手必勝または後手必勝のいずれか一方であることを示せ。

解答

(1) ある自然数 n に対し、ゲームが先手必勝でないとする。

このとき、 A はいかなる選択を行っても、 B が適切に選択を行っていけば、 A が勝利できないようにできる。しかし、このゲームは石を有限回取り除けば終了し、必ず勝者が決まるので、引き分けはない。よって、「A が勝利できない」とは「B が勝利できる」ということであり、これはこのゲームが後手必勝であることを意味する。

よって、どの自然数 n に対しても、このゲームは先手必勝または後手必勝のいずれか一方である。

別解

（注：数学的帰納法を用いて、もう少し詳しく書いたバージョンです）

(1) n 個の石から始めるゲームを「ゲーム n」と呼ぶことにする。

(i) $n=1$ のとき、A が1個の石を取り除けばいいので、「ゲーム $1$」は先手必勝である。

(ii) $n \leqq k$ のとき、各「ゲーム n」は先手必勝または後手必勝のいずれか一方であるとする。

「ゲーム $k+1$」について考える。また、以下では、 i は $k+1-i^2 \geqq 0$ を満たす自然数とする。

もし「ゲーム $k+1-i^2$」が後手必勝となる i があれば、A は $i^2$ 個の石を取り除けば必ず勝てるようにできるので、このゲームは先手必勝となる。
もし「ゲーム $k+1-i^2$」が後手必勝となる i がなければ、仮定より、どの i に対しても「ゲーム $k+1-i^2$」が先手必勝となる。これは A がどのように選択しても、必ず B が勝つようにできるということなので、このゲームは後手必勝となる。

以上から、「ゲーム $k+1$ 」も先手必勝または後手必勝となる。

(i)(ii) より、どの自然数 n に対しても、このゲームは先手必勝または後手必勝のいずれか一方である。

解答編つづき

問題

(2) $n=456$ のとき、このゲームは先手必勝であることを示せ。

解答

(2) まず A が　$21^2=441$ 個の石を取りのぞく。このとき、残りの石は15個。B が取り除ける石は、 1, 4, 9 のどれかである。次に B が何個取り除くかによって、場合分けをする。

(i) 1個取り除くとすると、残りの石は14個。 A が次に9個取り除くと、残りの石は5個。 B が1個取り除けば A が残りの4個を取り除いて A が勝利し、 B が4個取り除けば A が残りの1個を取り除いて A が勝利する。

(ii) 4個取り除くとすると、残りの石は11個。 A が次に9個取り除くと、残りの石は2個。 B は1個取り除くしかなく、 A が残りの1個を取り除いて A が勝利する。

(iii) 9個取り除くとすると、残りの石は6個。 A が次に4個取り除くと、残りの石は2個。 B は1個取り除くしかなく、 A が残りの1個を取り除いて A が勝利する。

(i)～(iii) より、 $n=456$ のとき、このゲームは先手必勝であることが示された。

解答編つづき

問題

(3) このゲームが後手必勝となる n は無限に多く存在することを示せ。

解答

(3) このゲームが後手必勝となる n が有限個であるとし、そうなる最大の自然数を N とおく。(1)より、 $n\gt N$ のとき、このゲームは先手必勝である。

$n=N^2+N+1$ とする。 $n\gt N$ なので、このときのゲームは先手必勝である。
\[ (N+1)^2-(N^2+N+1)=N \gt 0 \]なので、 A が取り除ける石の個数は、 $1$ 以上 $N^2$ 以下である。よって A が1回目を取り除いた直後、石は $N+1$ 個以上残っている。 $n\gt N$ のとき、このゲームは先手必勝であるから、このとき、 A がどのように選択しても B が勝利するようにできる。これは後手必勝ということであり、このゲームが先手必勝であることと矛盾する。

よって、後手必勝となる n は無限に多く存在する。

（解答終）