Back to Mathematical Olympiad
Difficulty: 5/102022 IMO 2022 (Q1)

The Bank of Oslo issues two types of coin: aluminium (denoted ) and bronze (denoted ). 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 -th coin from the left and moves all coins in that chain to the left end of the row.

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.

Options:

  • A.

    or : all pairs with or work.

  • B.

    or : all pairs with or work.

  • C.

    or : all pairs with or work.

  • or : all pairs with or work.

Guide / Hint

Hint 1: Consider what happens when the chain containing position is moved to the front. How does the configuration change?

Hint 2: For : the operation always moves a chain from the 'first half' to the front. Show this eventually collects one type.

Hint 3: For : construct an initial configuration that cycles. The chain at position alternates between types.

Solution

Step 1: When the operation moves a chain to the front, the relative order of the remaining coins is preserved. The chain at position determines the operation.

Step 2 (k <= n works): If , the -th coin is among the first positions. If the leftmost coins are not all the same type, there is a chain of one type that can be moved to the front, progressively sorting. Eventually all coins of one type accumulate at the front.

Step 3 (k = 2n works): The -th coin is the last one. Its chain gets moved to the front. This process eventually collects all coins of the last coin's type at the front.

Step 4 (n < k < 2n fails): Construct counterexample configurations where the process cycles without ever placing coins of the same type at the front.

Ready to track your progress and master these topics?

Create a free account
    2022 IMO 2022 Q1 - Olympiad Math Olympiad Question | Leminno