证 明 题（数学·2022年7月·国际数学奥林匹克）

The Bank of Oslo issues two types of coin：aluminium(denoted A) and bronze(denoted B). Marianne has n aluminium 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<2n, Marianne repeatedly performs the following operation：she identifies the longest chain containing the kth 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 AABBBABA would be

AAB↱B↲BABA→BBB↱A↲AABA→AAA↱B↲BBBA→BBB↱B↲AAAA.

Find all pairs (n, k) with 1 ≤ k ≤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<2n，玛丽安重复地进行如下操作：她找出包含(从左到右)第k枚硬币的最长链，然后把该链中所有货币移到序列最左端。

例如，n=4，k=4时，对于初始序列 AABBBABA，过程如下：

AAB↱B↲BABA→BBB↱A↲AABA→AAA↱B↲BBBA→BBB↱B↲AAAA.

求所有满足1≤k≤2n的数组(n，k)，使得对任意初始序列，都可以在有限次操作内使左端为n枚相同的货币。

解答提示

(1)当k<n时，构造，不合题意；(2)当k>⌈3/2 n⌉时，构造个，不符合题意；(3)当n≤k≤⌈3/2 n⌉时，考查硬币的总组数t，显然t单调不增.若前n个硬币始终不同，再分析t变为定值之后的操作，此时t≥3,设操作的这一组为“A…A”,形如：由于k≥n，所以P...

查看完整答案，请下载word版