Difference between revisions of "2022 IMO Problems/Problem 1"
(→See Also) |
|||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 11: | Line 11: | ||
[Video contains problem 1 discussion] | [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: | ||
| + | <cmath> k \notin \{1, 2, \ldots, n-1\} \cup \{\lceil \frac{3n}{2} \rceil + 1, \ldots, 2n\}. </cmath> | ||
| + | |||
| + | 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: | ||
| + | <cmath> A\ldots AB\ldots BA\ldots AB\ldots B\rightarrow B\ldots BA\ldots AB\ldots BA\rightarrow \ldots \blacksquare </cmath> | ||
| + | |||
| + | 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. <math>\blacksquare</math> | ||
| + | |||
| + | In conclusion, such pairs are \((n, k)\), where \(k \in \{n, n+1, \ldots, \lceil \frac{3n}{2} \rceil\}\). | ||
| + | |||
| + | |||
{{IMO box|year=2022|before=First Problem|num-a=2}} | {{IMO box|year=2022|before=First Problem|num-a=2}} | ||
Latest revision as of 12:05, 26 September 2024
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:
![\[k \notin \{1, 2, \ldots, n-1\} \cup \{\lceil \frac{3n}{2} \rceil + 1, \ldots, 2n\}.\]](http://latex.artofproblemsolving.com/6/d/a/6daec4b9eba2c332a77f76cec3c2b2c62a22a14a.png)
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\]](http://latex.artofproblemsolving.com/8/c/b/8cbfeff2fd681fb1e04de2db2a163f7aa6057fdb.png)
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\}\).
| 2022 IMO (Problems) • Resources | ||
| Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
| All IMO Problems and Solutions | ||
