MathLabs

第1题

奥斯陆银行发行两种硬币:铝币(记为 AA)和青铜币(记为 BB)。Marianne 有 nn 枚铝币和 nn 枚青铜币,按某种任意初始顺序排成一行。链是指由同类型连续硬币组成的任意子序列。给定固定正整数 k≤2nk\le2n,Marianne 反复执行以下操作:找出包含从左数第 kk 枚硬币的最长链,并把该链中所有硬币移到这一行的最左端。求所有满足 1≤k≤2n1\le k\le2n 的数对 (n,k)(n,k),使得对任意初始顺序,在操作过程的某个时刻,最左边的 nn 枚硬币都属于同一类型。
第 4/5 步:证明当 n≤k≤⌈3n/2⌉n\le k\le\lceil3n/2\rceil 时链数持续下降
n≤k≤⌈3n/2⌉ ⇒ chains keep merging until 2 remainn\le k\le\lceil3n/2\rceil\ \Rightarrow\ \text{chains keep merging until }2\text{ remain}
详细分析

若 kk 落在第一条链 [1,l][1,l](l≥k≥nl\ge k\ge n)中,则恰好 l=nl=n,这已经是所要的结论。若 kk 落在最后一条链中,抽屉原理的计数表明,只要链数至少为 44,就存在某条链的硬币数少于 2n−k+12n-k+1,因而不能始终包含保存 kk 的最后位置;因此 kk 最终必落入某条内部链(触发上一步的合并)或落入只剩 22 或 33 条链的局面,重复此论证会把链数降到 22,此时最左边的 nn 枚硬币属于同一类型。