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 AABBA remains the same.

For k>3n2=2nn2, we obtain the arrangement AABBAABB, where each basic chain consists of n2,n2,n2,n2 coins, respectively. Since the number of coins in the last chain is n2, 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 kB=[l,m], where l>1 and m<2n, the basic chains B1=[l,l1] and B2=[m+1,m] merge into one, and we are done since it is impossible to increase.

For kC=[1,l], where n+1>lkn, it holds that l=n, which is what we need to prove.

For kD=[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 < n2+12nk+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{n,n+1,,3n2}.


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