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が取り除ける石の 個数はl,4のいずれかである.Bが4個取り除くという選択を行うと,残りの石の個数は2となる. この状態においてAが取り除ける石の個数は1のみであり,その次にBが1個取り除いてBが 勝利する.

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

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

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

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

解答