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
AABBBABA→BBBAAABA→AAABBBBA→BBBBAAAA.
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,过程如下:
AABBBABA→BBBAAABA→AAABBBBA→BBBBAAAA.
求所有满足1≤k≤2n的数组(n,k),使得对任意初始序列,都可以在有限次操作内使左端为n枚相同的货币。