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
Claim:
Proof:
For
For
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
For
For
In conclusion, such pairs are
2022 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |