MathLabs

第4問

nn と kk を正の整数とする。Cathy は次のゲームを行う。11 から nn までの番号がついた nn 個のビー玉と kk 個の箱があり、最初はすべてのビー玉が一つの箱に入っている。各手番で Cathy は一つの箱を選び、その中で最小の番号（これを ii とする）をもつビー玉を、空の箱か、またはビー玉 i+1i+1 が入っている箱へ移す。ある時点でビー玉 nn だけが入った箱ができれば Cathy の勝ちである。Cathy が勝てるような整数の組 (n,k)(n,k) をすべて求めよ。
ステップ 2/4: n=2k−1n=2^{k-1} での達成可能性の帰納法
前のステップ次のステップ
n=2k−1 ⟹ Cathy can isolate marble n using k boxesn=2^{k-1}\ \Longrightarrow\ \text{Cathy can isolate marble }n\text{ using }k\text{ boxes}
詳しい解説

kk に関する帰納法で示す。k=1k=1, n=1n=1 は自明。mm 個の箱で 2m−12^{m-1} 個のビー玉を処理できると仮定し、m+1m+1 個の箱と 2m2^m 個のビー玉を考える。一つの箱 BB を空のまま残し、mm 個の箱を用いて開始の箱にビー玉 2m−1,…,2m2^{m-1},\ldots,2^m だけが残るまで mm 箱の必勝手順を行う。次に 2m−12^{m-1} を空の箱 BB に移し、BB を目標の箱として最初の手順を逆にたどると、1,…,2m−11,\ldots,2^{m-1} が BB に集まり、開始の箱には 2m−1+1,…,2m2^{m-1}+1,\ldots,2^m が残り、他の m−1m-1 個の箱が空く。最後に BB 以外の mm 個の箱を使って 2m−12^{m-1} 個のビー玉 2m−1+1,…,2m2^{m-1}+1,\ldots,2^m に mm 箱の戦略を適用すれば 2m2^m を孤立させられる。同じ戦略は任意の n≤2k−1n\le 2^{k-1} でも機能する。