2022 IMO Problems/Problem 1


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


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.


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\}\).

See Also

2022 IMO (Problems) • Resources
Preceded by
First Problem
1 2 3 4 5 6 Followed by
Problem 2
All IMO Problems and Solutions