IMO 2022 Shortlist C2
The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted A) and copper (denoted C). Morgane has ...
Category: Combinatorics
Problem
The Bank of Oslo issues coins made out of two types of metal: aluminium (denoted A) and copper (denoted C). Morgane has n aluminium coins, and n copper coins, and arranges her 2n coins in a row in some arbitrary initial order. Given a fixed positive integer k ď 2n, she repeatedly performs the following operation: identify the largest subsequence containing the k-th coin from the left which consists of consecutive coins made of the same metal, and move all coins in that subsequence to the left end of the row. For example, if n “ 4 and k “ 4, the process starting from the configuration AACCCACA would be AACCCACA Ñ CCCAAACA Ñ AAACCCCA Ñ CCCCAAAA Ñ ¨¨¨ . Find all pairs pn,kq with 1 ď k ď 2n such that for every initial configuration, at some point of the process there will be at most one aluminium coin adjacent to a copper coin. (France)