奥斯陆银行发行两种硬币:铝币(记为 A)和青铜币(记为 B)。Marianne 有 n 枚铝币和 n 枚青铜币,按某种任意初始顺序排成一行。链是指由同类型连续硬币组成的任意子序列。给定固定正整数 k≤2n,Marianne 反复执行以下操作:找出包含从左数第 k 枚硬币的最长链,并把该链中所有硬币移到这一行的最左端。求所有满足 1≤k≤2n 的数对 (n,k),使得对任意初始顺序,在操作过程的某个时刻,最左边的 n 枚硬币都属于同一类型。
若 k 落在第一条链 [1,l](l≥k≥n)中,则恰好 l=n,这已经是所要的结论。若 k 落在最后一条链中,抽屉原理的计数表明,只要链数至少为 4,就存在某条链的硬币数少于 2n−k+1,因而不能始终包含保存 k 的最后位置;因此 k 最终必落入某条内部链(触发上一步的合并)或落入只剩 2 或 3 条链的局面,重复此论证会把链数降到 2,此时最左边的 n 枚硬币属于同一类型。