# 2022 IMO Problems/Problem 1

## Problem

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\le 2n$, Marianne repeatedly performs the following operation: she identifies the longest chain containing the $k^{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 AABBBABA would be

AABBBABA → BBBAAABA → AAABBBBA → BBBBAAAA → BBBBAAAA → ...

Find all pairs $(n, k)$ with $1 \le k \le 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

https://www.youtube.com/watch?v=nYD-qIOdi_c [Video contains solutions to all day 1 problems] https://youtu.be/KHn3xD6wS3A [Video contains problem 1 discussion]

We call a chain basic when it is the largest possible for the coins it consists of. Let $$A=[i,j]$$ be the basic chain with the $$i$$-th and $$j$$-th coins being the first and last, respectively.

Claim: $$k \notin \{1, 2, \ldots, n-1\} \cup \{\lceil \frac{3n}{2} \rceil + 1, \ldots, 2n\}.$$

Proof: For $$k < n$$, it is easy to see that the arrangement $$A\ldots AB\ldots BA$$ remains the same.

For $$k > \lceil \frac{3n}{2} \rceil = 2n - \lfloor \frac{n}{2} \rfloor$$, we obtain the arrangement $$A\ldots AB\ldots BA\ldots AB\ldots B$$, where each basic chain consists of $$\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil, \lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor$$ coins, respectively. Since the number of coins in the last chain is $$\geq \lfloor \frac{n}{2} \rfloor$$, it follows that $$k$$ is greater than the number of the remaining coins, or in other words, it is always contained in the last chain.

However, we have a loop: $$A\ldots AB\ldots BA\ldots AB\ldots B\rightarrow B\ldots BA\ldots AB\ldots BA\rightarrow \ldots \blacksquare$$

We will prove that in any other case, the number of basic chains decreases by a constant, which proves the claim.

For $$k \in B=[l, m]$$, where $$l > 1$$ and $$m < 2n$$, the basic chains $$B_1=[l{'}, l-1]$$ and $$B_2=[m+1, m']$$ merge into one, and we are done since it is impossible to increase.

For $$k \in C=[1, l]$$, where $$n + 1 > l \geq k \geq n$$, it holds that $$l = n$$, which is what we need to prove.

For $$k \in D=[m, 2n]$$, we will prove that the basic chains are of quantity 2 or 3 (two are obtained with one move): Indeed, if there are at least 4 basic chains, from the beginning of the pigeonhole, we have at least one chain with a number of coins < $$\lfloor \frac{n}{2} \rfloor + 1 \leq 2n - k + 1$$. Therefore, $$k$$ does not belong to this chain when it is the last, and then the number of basic chains decreases, which completes the proof. $\blacksquare$

In conclusion, such pairs are $$(n, k)$$, where $$k \in \{n, n+1, \ldots, \lceil \frac{3n}{2} \rceil\}$$.