63rd International Mathematical Olympiad - IMO 2022 | Problem 1 - Solution - 13 July 2022

Problem 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$ , Marianne repeatdly performs the following operation: he identifies the longest chain containing the $k^{th}$ coin from the left and moves all coins in that chain to 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 \to BBBAAABA \to AAABBBBA \to BBBBAAAA \to ...$

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.

Solution

Define a word to be a sequence of $A'$ s and $B'$ s representing Marianne's row of coins.

We claim that the answer is all ordered pairs $(n,k)$ such that $n\le k\le 2n-\lfloor \frac{n}{2}\rfloor.$

First, for $n=1,$ clearly both $(1,1)$ and $(1,2)$ work.

Now, assume that $n\ge 2$ and $1\le k\le n-1.$ We first show that all such ordered pairs $(n,k)$ don't work. If the word started with $k$ $A'$ s followed by a $B,$ then clearly Marianne's operation never changes the word, so all such ordered pairs $(n,k)$ don't work.

We now show that all ordered pairs $(n,k)$ with $2n-\lfloor \frac{n}{2}\rfloor+1\le k\le 2n$ don't work. Consider the word $AA\ldots ABB\ldots BAA\ldots ABB\ldots B,$ where the first string of $A'$ s has length $\lfloor \frac{n}{2}\rfloor,$ the first string of $B'$ s has length $\lfloor \frac{n}{2}\rfloor,$ the second string of $A'$ s has length $\lceil \frac{n}{2}\rceil,$ and the second string of $B'$ s has length $\lceil \frac{n}{2}\rceil.$ Note that since $n\ge 2,$ $\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2}\rceil \le n.$ Denote this word by $C_1C_2C_3C_4,$ where $C_i$ denotes the $i^\text{th}$ string of the word. Then, because of the bounds on $k,$ Marianne's operation would result in the process $C_1C_2C_3C_4, C_4C_1C_2C_3, C_3C_4C_1C_2, C_2C_3C_4C_1, C_1C_2C_3C_4,$ which never results in a situation where the $n$ leftmost coins are the same type.

Now we tackle the case where $n\ge 2$ and $n\le k\le 2n-\lfloor \frac{n}{2}\rfloor.$ Define the score of a word to be the number of instances of two consecutive letters being $AA$ or $BB.$ For instance, the score of $AABBAABB$ is $4$ and the score of $AAAABBBB$ is $6.$ We present a claim.

Claim: Under Marianne's operation, the score of a word never decreases. To do so, we use the following lemma:

Lemma: When we join at least two chains of the same letter together to form a large chain, the score of the large chain is larger than the sum of the scores of the smaller chains.

Proof: Let the lengths of the smaller chains be $i_1,i_2,\ldots i_j.$ Note that the score of a chain with length $i$ is $i-1,$ so the sum of the scores of the smaller chains is $i_1+i_2+\cdots+i_j-j.$ However, the composition of these chains has length $i_1+i_2+\cdots+i_j,$ so its score is $i_1+i_2+\cdots+i_j-1,$ and since $j>1$ by assumption, the lemma is proven.

When Marianne performs her operation, none of the initial chains are broken, and there may be linkings of chains of the same letter to form larger chains. Combining this observation with our lemma, our claim is proven.

Again using our lemma, we see that the words of fixed length $2n$ with the largest score are $AA\ldots ABB\ldots B$ and $BB\ldots BAA\ldots A,$ where each string of $A'$ s and $B'$ s has length $n.$

Now, we are ready to show that all ordered pairs $(n,k)$ such that $n\le k\le 2n-\lfloor \frac{n}{2}\rfloor$ work. It suffices to show that there isn't a word $W$ (other than $AA\ldots ABB\ldots B$ and $BB\ldots BAA\ldots A$ ) such that, no matter how many operations Marianne performs on $W,$ the score of $W$ doesn't increase.

Assume for the sake of contradiction that such a $W$ exists. Let the leftmost letter of the chain Marianne moves during her first operation be the $x^\text{th}$ letter of $W$ and the rightmost letter of the chain she is moving be the $y^\text{th}$ letter of $W.$ WLOG, let this chain contain $A'$ s. If $x\ge 2$ and $y\le 2n-1,$ then the $(x-1)^\text{th}$ letter of $W$ and the $(y+1)^\text{th}$ letter of $W$ are $B'$ s by the assumption that the chain is optimal. Then, when Marianne moves the chain, the $B'$ s are joined together, and by our lemma, this increases the score of $W.$ Hence, either $x=1$ or $y=2n.$

Now, we split into cases.

Case 1: $k=n.$ Then, clearly $y\neq 2n$ as the maximum length of the chain is $n.$ Hence $x=1.$ However, this implies that $W=AA\ldots ABB\ldots B,$ where each string of $A'$ s and $B'$ has length $n,$ contradicting the assumption that $W$ wasn't $AA\ldots ABB\ldots B,$ where string of $A'$ s and $B'$ s has length $n.$

Case 2: $k=n+1.$ Then, clearly $x\neq 1$ as the maximum length of the chain is $n.$ Hence $y=2n.$ However, this implies that $W=BB\ldots BAA\ldots A,$ where each string of $A'$ s and $B'$ s has length $n,$ contradicting the assumption that $W$ wasn't $BB\ldots BAA\ldots A,$ where each string of $A'$ s and $B'$ s has length $n.$

Case 3: $n+2\le k\le 2n-\lfloor \frac{n}{2}\rfloor.$ As in case $2,$ $y=2n.$ Additionally, the length of any chain that Marianne moves cannot have length $n,$ because if a chain Marianne moves did have length $n,$ the word formed would start with $n$ instances of the same letter. Let $W=C_1C_2\ldots C_j,$ where the $C_i'$ s are the strings of identical letters in $W.$

At every moment, the chain Marianne moves must contain the both the $2n-\lfloor \frac{n}{2}\rfloor^\text{th}$ letter and the $2n^\text{th}$ letter. Hence every chain Marianne moves must have length at least $\lfloor \frac{n}{2}\rfloor+1$ letters. Additionally, since the chain Marianne moves must contain the $2n^\text{th}$ letter and be of maximal length, the chains Marianne moves must be $C_j, C_{j-1}, C_{j-2},\ldots, C_1,$ in that order. We thus have that each $C_i$ has length at least $\lfloor \frac{n}{2}\rfloor+1$ but less than $n.$

However, this leads to a contradiction! A subset of the $C_i'$ s must contain all of the $n$ $A'$ s, but this is impossible if every $C_i$ has length at least $\lfloor \frac{n}{2}\rfloor+1$ but less than $n.$ This is because $2$ $C_i'$ s would contain more than $n$ letters, while $1$ $C_i$ would contain less than $n$ letters.

We are done.