2022 IMO 第 1 题

The Bank of Oslo issues two types of coin: aluminum (denoted $A$ ) and bronze (denoted $B$ ). Marianne has $n$ aluminum coins and $n$ bronze coins arranged in a row in some arbitrary initial order. A chain is any subsequence of consecutive coins of the same type. Given a fixed positive integer $k \leq 2n$ , Gilberty repeatedly performs the following operation: he identifies the longest chain containing the $k^{\mathrm{th}}$ coin from the left and moves all coins in that chain to the left end of the row. For example, if $n = 4$ and $k = 4$ , the process starting from the ordering $AABBBA$ would be $AABBBA$ $A$ $BBBA$ $A$ $AAABBB$ $A$ $BBBBAA$ $A$ $BBBBAA$ $A$ $\dots$

Find all pairs $(n,k)$ with $1\leq k\leq 2n$ such that for every initial ordering, at some moment during the process, the leftmost $n$ coins will all be of the same type.

奥斯陆银行发行两种硬币：铝币(记为 $A$ )和铜币(记为 $B$ )。玛丽安有 $n$ 铝币和 $n$ 铜币，按任意初始顺序排列成一排。链是相同类型的连续硬币的任何子序列。给定一个固定的正整数 $k \leq 2n$ ，Gilberty 重复执行以下操作：他从左侧找出包含 $k^{\mathrm{th}}$ 硬币的最长链，并将该链中的所有硬币移动到该行的左端。例如，如果 $n = 4$ 且 $k = 4$ ，则从排序 $AABBBA$ 开始的过程将为 $AABBBA$ $A$ $BBBA$ $A$ $AAABBB$ $A$ $BBBBAA$ $A$ $BBBBAA$ $A$ $\dots$

找到所有 $(n,k)$ 与 $1\leq k\leq 2n$ 的对，这样对于每个初始排序，在过程中的某个时刻，最左边的 $n$ 硬币都将属于相同类型。