A, Bの2人が石取りゲームを行う。初期状態で台の上に $n$ 個の石があり、交互に石を取り除いていく。一度に取り除く石の個数は自然数の2乗でなければならない。最後に石を取り除いた方が勝ちである。 (1) 任意の自然数 $n$ に対して、このゲームは先手必勝か後手必勝のいずれかであることを示す。 (2) $n=456$ のとき、このゲームは先手必勝であることを示す。

1. 問題の内容

A, Bの2人が石取りゲームを行う。初期状態で台の上に $n$ 個の石があり、交互に石を取り除いていく。一度に取り除く石の個数は自然数の2乗でなければならない。最後に石を取り除いた方が勝ちである。

(1) 任意の自然数 $n$ に対して、このゲームは先手必勝か後手必勝のいずれかであることを示す。

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

2. 解き方の手順

(1) ゲームの構造上、どちらかのプレイヤーが必ず勝つので、先手必勝または後手必勝のいずれかである。なぜなら、有限個の石から開始し、石の数が減っていくので、必ずゲームは終了する。ゲームが終了するということは、どちらかのプレイヤーが最後の石を取って勝利するということなので、先手必勝または後手必勝のいずれかである。

(2) $n=456$ のとき、先手Aが必勝であることを示す。

まず、$456$ から $1$ から順に2乗数を引いていくことを考える。

$456 - 1 = 455$

$456 - 4 = 452$

$456 - 9 = 447$

$456 - 16 = 440$

$456 - 25 = 431$

$456 - 36 = 420$

$456 - 49 = 407$

$456 - 64 = 392$

$456 - 81 = 375$

$456 - 100 = 356$

$456 - 121 = 335$

$456 - 144 = 312$

$456 - 169 = 287$

$456 - 196 = 260$

$456 - 225 = 231$

$456 - 256 = 200$

$456 - 289 = 167$

$456 - 324 = 132$

$456 - 361 = 95$

$456 - 400 = 56$

$456 - 441 = 15$

$n$ が小さい場合から考える。

$n = 1$ ならば、$1=1^2$なので、Aは1を取り、先手必勝。

$n = 2$ ならば、$1^2$しか取れないので、Aは1を取り、残り1となる。Bは1を取り、Bが勝ちなので、後手必勝。

$n = 3$ ならば、$1^2$しか取れないので、Aは1を取り、残り2となる。Bは1を取り、残り1となる。Aは1を取り、Aが勝ちなので、先手必勝。

$n = 4$ ならば、$1^2$または$2^2$が取れる。Aが$2^2$を取ると残り0で、Aが勝ちなので、先手必勝。

$n = 5$ ならば、$1^2$または$2^2$が取れる。Aが$2^2$を取ると残り1となる。Bは1を取り、Bが勝ちなので、Aが$2^2$を取るとAが負ける。Aが$1^2$を取ると残り4となり、Bは$2^2$を取り、Bが勝ちとなる。つまり後手必勝。

$n=6$なら、Aが$1^2$を取ると残り5。先程$n=5$は後手必勝だったからAが負ける。Aが$2^2$を取ると残り2。$n=2$は後手必勝なのでAが負ける。後手必勝。

先手必勝の状態にできるなら先手必勝、そうでなければ後手必勝。

$456 \equiv 0 \pmod 3$なのでAが$1,4,9,16,\dots$を取って$456 - x^2 \equiv 0 \pmod 3$とすればBはそれを崩すように$1,4,9,16,\dots$を取るはずなので、これでうまくいくかはわからない。

$n = 456$の場合、先手Aが$x^2$個の石を取った時、残りの石の数が後手必勝となるような$x$が存在すれば、Aは負ける。そのような$x$が存在しなければ、Aは勝てる。

$n = 456$から、$1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441$を引いた数が後手必勝でないことを示せば良い。

$456=21^2 + 15$

$456 = 2^3 \cdot 3 \cdot 19$

結論から言うと、Aは最初に$4=2^2$個の石を取れば、残り$452$個となる。以後、Bが$x^2$個の石を取ったならば、Aは$x^2$個の石を取るという戦略を取ると、常に残り個数は$452 - 2x^2$となる。これを繰り返していけば、最終的にAが最後の石を取って勝つことができる。

3. 最終的な答え

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

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