MathLabs

第4問

nn と kk を正の整数とする。Cathy は次のゲームを行う。11 から nn までの番号がついた nn 個のビー玉と kk 個の箱があり、最初はすべてのビー玉が一つの箱に入っている。各手番で Cathy は一つの箱を選び、その中で最小の番号(これを ii とする)をもつビー玉を、空の箱か、またはビー玉 i+1i+1 が入っている箱へ移す。ある時点でビー玉 nn だけが入った箱ができれば Cathy の勝ちである。Cathy が勝てるような整数の組 (n,k)(n,k) をすべて求めよ。
ステップ 4/4: 中間のビー玉を除いて帰納法を完結する
Delete 2,…,2m−1 ⟹ 2m−1+1 marbles win in m boxes, contradiction ⟹ n≤2k−1\text{Delete }2,\ldots,2^{m-1}\ \Longrightarrow\ 2^{m-1}+1\text{ marbles win in }m\text{ boxes, contradiction}\ \Longrightarrow\ n\le 2^{k-1}
詳しい解説

ここで XX 以降の手順からビー玉 2,…,2m−12,\ldots,2^{m-1} を取り除く。するとビー玉 11 は空の箱から空の箱へと移るだけで、常に一つの箱を占有し、≥2m−1+1\ge 2^{m-1}+1 のビー玉がその箱に入るのを妨げる。したがって残りの 2m−1+12^{m-1}+1 個のビー玉(すなわち 2m−1+1,…,2m+12^{m-1}+1,\ldots,2^m+1)は残りの mm 個の箱だけを使って 2m+12^m+1 を孤立させることになり、再び帰納法の仮定に反する。ゆえに n≥2k−1+1n\ge 2^{k-1}+1 では勝てず、Cathy が勝てるのは n≤2k−1n\le 2^{k-1} のとき、かつそのときに限る。