MathLabs

第1题

奥斯陆银行发行两种硬币：铝币（记为 AA）和青铜币（记为 BB）。Marianne 有 nn 枚铝币和 nn 枚青铜币，按某种任意初始顺序排成一行。链是指由同类型连续硬币组成的任意子序列。给定固定正整数 k≤2nk\le2n，Marianne 反复执行以下操作：找出包含从左数第 kk 枚硬币的最长链，并把该链中所有硬币移到这一行的最左端。求所有满足 1≤k≤2n1\le k\le2n 的数对 (n,k)(n,k)，使得对任意初始顺序，在操作过程的某个时刻，最左边的 nn 枚硬币都属于同一类型。
第 3/5 步：若 kk 严格落在某条链内部，两条链会合并
上一步下一步
通俗地说

把中间的一条链移到最前面，会把其两侧同类型的相邻链合并为一条，所以链的总数只会减少。

B1=[l′,l−1],B2=[m+1,m′]B_1=[l',l-1],\quad B_2=[m+1,m']
详细分析

设 kk 落在链 [l,m][l,m]（l>1l>1 且 m<2nm<2n，既非第一条也非最后一条链）内部。将 [l,m][l,m] 移到最前面后，其前面紧邻的链 B1=[l′,l−1]B_1=[l',l-1] 与后面紧邻的链 B2=[m+1,m′]B_2=[m+1,m'] 变为相邻；由于 B1B_1 与 B2B_2 是同一硬币类型，它们合并为一条链，链的总数严格减少。