第4問

n

と

k

を正の整数とする。Cathy は次のゲームを行う。

1

から

n

までの番号がついた

n

個のビー玉と

k

個の箱があり、最初はすべてのビー玉が一つの箱に入っている。各手番で Cathy は一つの箱を選び、その中で最小の番号（これを

i

とする）をもつビー玉を、空の箱か、またはビー玉

i+1

が入っている箱へ移す。ある時点でビー玉

n

だけが入った箱ができれば Cathy の勝ちである。Cathy が勝てるような整数の組

(n,k)

をすべて求めよ。

ステップ 3/4: 手 X 以降の分離

前のステップ次のステップ

n=2^{k-1}+1\ \Longrightarrow\ \text{after the last exit }X\text{ of }2^{m-1}+1,\text{ marble }1\text{ never meets }\ge 2^{m-1}+1

詳しい解説

$k$ に関する帰納法で $n=2^{k-1}+1$ では勝てないことを示す。 $k=1$ , $n=2$ は箱が一つしかなく動かせないので明らか。 $m$ 個の箱では $2^{m-1}+1$ 個のビー玉で勝てないと仮定し、 $m+1$ 個の箱で $2^m+1$ 個のビー玉なら勝てると仮定して矛盾を導く。ビー玉 $2^{m-1}+1$ が開始の箱を最後に離れる手を $X$ とする。 $X$ の後、ビー玉 $1,\ldots,2^{m-1}+1$ がすべて同じ箱に入ることはあり得ない。もし入ったとすると、その時点から $X$ まで手順を逆転し $>2^{m-1}+1$ のビー玉を無視することで、開始の箱以外の $m$ 個の箱だけで $2^{m-1}+1$ 個のビー玉に対する必勝手順が得られ（ $X$ 以降、開始の箱には常に $>2^{m-1}+1$ のビー玉が残っているため）、帰納法の仮定に反する。各箱は常に連続区間をなすから、 $X$ 以降はビー玉 $1$ が $\ge 2^{m-1}+1$ のどのビー玉とも同じ箱に入ることはない。