MathLabs

第1题

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

结合两个不可行的构造与合并论证，总能成功的数对恰好是满足 n≤k≤⌈3n/2⌉n\le k\le\lceil3n/2\rceil 的那些。