MathLabs

第1题

奥斯陆银行发行两种硬币：铝币（记为 AA）和青铜币（记为 BB）。Marianne 有 nn 枚铝币和 nn 枚青铜币，按某种任意初始顺序排成一行。链是指由同类型连续硬币组成的任意子序列。给定固定正整数 k≤2nk\le2n，Marianne 反复执行以下操作：找出包含从左数第 kk 枚硬币的最长链，并把该链中所有硬币移到这一行的最左端。求所有满足 1≤k≤2n1\le k\le2n 的数对 (n,k)(n,k)，使得对任意初始顺序，在操作过程的某个时刻，最左边的 nn 枚硬币都属于同一类型。
第 2/5 步：用四链循环排除 k>⌈3n/2⌉k>\lceil3n/2\rceil
上一步下一步
⌊n/2⌋, ⌈n/2⌉, ⌈n/2⌉, ⌊n/2⌋\lfloor n/2\rfloor,\ \lceil n/2\rceil,\ \lceil n/2\rceil,\ \lfloor n/2\rfloor
详细分析

当 k>⌈3n/2⌉k>\lceil3n/2\rceil 时，取大小为 ⌊n/2⌋,⌈n/2⌉,⌈n/2⌉,⌊n/2⌋\lfloor n/2\rfloor,\lceil n/2\rceil,\lceil n/2\rceil,\lfloor n/2\rfloor 且按 A,B,A,BA,B,A,B 交替的四条链；由于最后一条链至少有 ⌊n/2⌋\lfloor n/2\rfloor 枚硬币，kk 总落在其中，把它移到最前面只是让四条链循环，因此模式永远重复，最左边的 nn 枚永远不会同类型。