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]