第4题

设

n

与

k

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

n

颗弹珠和

k

个盒子，弹珠编号为

1

到

n

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

i

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

i+1

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

n

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

(n,k)

。

第 1/4 步：连续区间不变量与可逆性

\text{Every non-empty box holds a consecutive interval }\{a,a+1,\ldots,b\};\ \text{moves are reversible}

详细分析

初始时起始盒装有 $\{1,\ldots,n\}$ 。由于 Cathy 每次只取出某盒的最小元，放入空盒或接到另一盒的最小元 $i+1$ 上，每个非空盒始终装有一段连续编号，且每一步合法操作的逆操作仍然合法。