Difference between revisions of "2022 IMO Problems/Problem 1"

Latest revision as of 13:05, 26 September 2024

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

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

@@ Line 36: / Line 36: @@
 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
 {{IMO box|year=2022|before=First Problem|num-a=2}}

Page

Toolbox

Search

Difference between revisions of "2022 IMO Problems/Problem 1"

Latest revision as of 13:05, 26 September 2024

Problem

Solution