第4题

设

n

与

k

为正整数。Cathy 玩如下游戏：有

n

颗弹珠和

k

个盒子，弹珠编号为

1

到

n

。初始时所有弹珠都放在同一个盒子里。每一步，Cathy 选择一个盒子，把其中编号最小的弹珠（设为

i

）移到任意一个空盒，或移到装有弹珠

i+1

的盒子。若在某一时刻有一个盒子只装有弹珠

n

，则 Cathy 获胜。求所有使 Cathy 能获胜的整数对

(n,k)

。

第 2/4 步：对

n=2^{k-1}

可达性的归纳

上一步下一步

n=2^{k-1}\ \Longrightarrow\ \text{Cathy can isolate marble }n\text{ using }k\text{ boxes}

详细分析

对 $k$ 归纳； $k=1$ 、 $n=1$ 显然。设 $m$ 个盒子可处理 $2^{m-1}$ 颗弹珠，考虑 $m+1$ 个盒子与 $2^m$ 颗弹珠。保留一个空盒 $B$ ，用其余 $m$ 个盒子执行 $m$ 盒必胜序列，直到起始盒中只剩弹珠 $2^{m-1},\ldots,2^m$ 。把 $2^{m-1}$ 移入空盒 $B$ ，再以 $B$ 为目标盒逆向执行初始序列；这会把 $1,\ldots,2^{m-1}$ 汇集到 $B$ 中，起始盒留下 $2^{m-1}+1,\ldots,2^m$ ，并腾空其余 $m-1$ 个盒子。最后用 $B$ 以外的 $m$ 个盒子对 $2^{m-1}$ 颗弹珠 $2^{m-1}+1,\ldots,2^m$ 施用 $m$ 盒策略即可孤立 $2^m$ 。同一策略对任意 $n\le 2^{k-1}$ 同样有效。