なかけんの数学ノート

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

問題編

問題

 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)よりある自然数から先は先手必勝ばかりになってしまいますが、その中に後手必勝のゲームが作れてしまうことを示しましょう。

次のページへ進む ⇒

[広告]
試験名: 大学入試, 京大特色, 京都大学
年度: 2017年度
分野: 集合と命題
トピック: 集合と命題
レベル: ややむずい
キーワード: 存在, 無数に存在
更新日:2016/12/03