2017年入試問題研究に戻る京大特色3番
A，Bのの2人が次のゲームを行う．初期状態として，台の上に $ n $ 個の石が置いてある． 最初にA，次にBの順で交互に，台から1個以上の石を取り除いていく． ただし一度に取り除くく個数は自然数の2乗でなければならない． 台の上に石がない状態にした方を勝者として，そこでゲームを終了する．
このゲームが先手必勝であるとは，Aが自分の番で取り除く石の個数を適切に選択していけば， Bがいかなる選択を行っても，必ずAが勝利できることとする． 同様に，このゲームが後手必勝であるとは，Bが自分の番で適切に選択を行っていけば， Aがいかなる選択を行っても必ずBが勝利できることとする．
例えば， $ n=10 $ のとき，最初にAが取り除ける石の個数は1，4，9のいずれかである．
● Aが１個取り除くならば，残りの石の個数は9となる． この状態においてBが取り除ける石の個数は1，4，9のいずれかである． Bが9個取り除くという選択を行うとBが勝利する．
● Aが9個取り除くならば，残りの石の個数は1となる．次にＢが1個取り除いてBが勝利する．
● Aが4個取り除くならば，残りの石の個数は6となる．この状態においてBが取り除ける石の 個数はl，4のいずれかである．Bが4個取り除くという選択を行うと，残りの石の個数は2となる． この状態においてAが取り除ける石の個数は1のみであり，その次にBが１個取り除いてBが 勝利する．
したがって，Bが自分の番で取り除く石の個数を適切に選択していけば， 必ずBが勝利できるので， $ n=10 $ のときのゲームは後手必勝である．
以下の設問に答えよ．(1) どの自然数 $ n $ に対しても，このゲームは先手必勝または後手必勝のいずれか一方であることを示せ．
(2) $ n=456 $ のとき，このゲームは先手必勝であることを示せ．
(3) このゲームが後手必勝となる $ n $ は無限に多く存在することを示せ．