2022 IMO Problems/Problem 1

Problem

The Bank of Oslo issues two types of coin: aluminium (denoted A) and bronze (denoted B). Marianne has aluminium coins and 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 , Marianne repeatedly performs the following operation: she identifies the longest chain containing the coin from the left, and moves all coins in that chain to the left end of the row. For example, if and , the process starting from the ordering AABBBABA would be

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

Find all pairs with such that for every initial ordering, at some moment during the process, the leftmost 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:

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:

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.

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

See Also

\( 10: 09 \) \( 15 \% \) 目

SO KISLAY \[ \int e^{\left(-x^{2}\right) / 2} d x=\int e^{-(x / \sqrt{2})^{2}} d x \]

Substitute \( u=\frac{x}{\sqrt{2}} \rightarrow d x=\sqrt{2} d u \) in above equation, \[ \begin{array}{l} \int e^{-(x / \sqrt{2})^{2}} d x=\int e^{-(u)^{2}} \sqrt{2} d u=\sqrt{2} \int e^{-(u)^{2}} d u \\ \because \int a . f(x) d x=a \int f(x) d x \end{array} \]

Use the common integral \( \int e^{-u^{2}} d u=\frac{\sqrt{\pi}}{2} \operatorname{erf}(u) \), we get \[ \sqrt{2} \int e^{-u^{2}} d u=\sqrt{2} \frac{\sqrt{\pi}}{2} \operatorname{erf}(u) \]

Substitute back \( u=\frac{x}{\sqrt{2}} \), we get \[ \sqrt{2} \frac{\sqrt{\pi}}{2} \operatorname{erf}(u)=\sqrt{2} \frac{\sqrt{\pi}}{2} \operatorname{erf}\left(\frac{x}{\sqrt{2}}\right) \]

Also, \[ \sqrt{2} \frac{\sqrt{\pi}}{2} \operatorname{erf}\left(\frac{x}{\sqrt{2}}\right)=\sqrt{\frac{\pi}{2}} \operatorname{erf}\left(\frac{x}{\sqrt{2}}\right)+C \] where \( C \) is an integration constant. NOTE: The \( \operatorname{erf}(x) \) or error function (also called the Gauss error function) is a special function (non-elementary) of sigmoid shape. It is defined as \[ \operatorname{erf}(x)=\frac{1}{\sqrt{\pi}} \int_{-x}^{x} e^{-t 2} d t \] AI ALISHINEIA

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