第1题

奥斯陆银行发行两种硬币：铝币（记为

A

）和青铜币（记为

B

）。Marianne 有

n

枚铝币和

n

枚青铜币，按某种任意初始顺序排成一行。链是指由同类型连续硬币组成的任意子序列。给定固定正整数

k\le2n

，Marianne 反复执行以下操作：找出包含从左数第

k

枚硬币的最长链，并把该链中所有硬币移到这一行的最左端。求所有满足

1\le k\le2n

的数对

(n,k)

，使得对任意初始顺序，在操作过程的某个时刻，最左边的

n

枚硬币都属于同一类型。

第 1/5 步：用一个不变排列排除

k<n

通俗地说

当 $k$ 较小时，某种排列可以让第 $k$ 枚硬币永远停留在一条太短而无法完全到达左端的链中。

A\ldots A\,B\ldots B\,A

详细分析

当 $k<n$ 时，取初始排列 $A\ldots A\,B\ldots B\,A$ （一段 $A$ ，接着全部 $n$ 枚 $B$ ，最后一枚 $A$ ），使第 $k$ 枚硬币始终位于开头较长的 $A$ 链中；执行操作只会把同一条链移到最前面，排列保持不变，故最左边的 $n$ 枚永远不会同类型。