MathLabs

第4题

设 nn 与 kk 为正整数。Cathy 玩如下游戏:有 nn 颗弹珠和 kk 个盒子,弹珠编号为 11 到 nn。初始时所有弹珠都放在同一个盒子里。每一步,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}。