IMO 2022 · Problem 1

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 \leqslant 2n\), Marianne repeatedly performs the following operation: she identifies the longest chain containing the \(k^{\text{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

\[ AAB\underline{B}BABA \to BBB\underline{A}AABA \to AAA\underline{B}BBBA \to BBB\underline{B}AAAA \to BBB\underline{B}AAAA \to \cdots. \]

Find all pairs \((n,k)\) with \(1 \leqslant k \leqslant 2n\) such that for every initial ordering, at some moment during the process, the leftmost \(n\) coins will all be of the same type.

Official text of the problem. Official problem paper (PDF)

Answer

All pairs of positive integers \((n,k)\) satisfying \[ \boxed{n\leqslant k\leqslant \left\lceil\frac{3n}{2}\right\rceil}. \]

Solution

Call a maximal chain a block. Thus the row is uniquely divided into blocks whose types alternate, and each operation moves the entire block containing position \(k\) to the front. Write \(A^a\) or \(B^a\) for \(a\) consecutive coins of the indicated type.

First we exclude the values of \(k\) outside the claimed range.

If \(k<n\), then \(n\geqslant2\). Consider \[ A^{n-1}B^nA. \] Position \(k\) belongs to the first block, so every operation leaves this row unchanged. Its leftmost \(n\) coins are not all of the same type.

Now suppose \[ k>\left\lceil\frac{3n}{2}\right\rceil. \] Again \(n\geqslant2\). Put \[ a=\left\lfloor\frac n2\right\rfloor, \qquad b=\left\lceil\frac n2\right\rceil, \] and start with \[ A^aB^aA^bB^b. \] These are four alternating blocks, each of length at least \(a\). Since \[ k> \left\lceil\frac{3n}{2}\right\rceil=2n-a, \] position \(k\) belongs to the last block whenever that block has length at least \(a\). Moving the last block to the front simply rotates the four blocks, without merging any of them. Consequently, this description remains valid forever: every operation rotates the same four blocks.

The first block always has length \(a\) or \(b\), both strictly less than \(n\). Thus this initial ordering never satisfies the requirement.

It remains to prove that every \[ n\leqslant k\leqslant\left\lceil\frac{3n}{2}\right\rceil \] works. Fix such a \(k\), and suppose, for a contradiction, that some initial ordering never has its leftmost \(n\) coins all of the same type.

At every stage, the first block then has length at most \(n-1<k\), so the selected block is never the first block. Let \(r\) denote the current number of blocks. We examine how \(r\) changes.

  • If the selected block is neither the first nor the last, removing it joins its two neighbours, which have the same type. Thus removal reduces the number of blocks by two. Putting the removed block at the front adds at most one block, so the operation strictly decreases \(r\).
  • If the selected block is the last, removing it reduces the number of blocks by one. Putting it at the front restores that block precisely when its type differs from the first block’s type; otherwise, it merges with the first block. Hence \(r\) stays unchanged exactly when the first and last blocks have different types, which is equivalent to \(r\) being even.

Therefore the number of blocks never increases. Being a positive integer, it must eventually remain constant. From that point onward, every operation moves the last block to the front, and the constant number \(r\) of blocks is even.

There cannot be just two blocks: since there are exactly \(n\) coins of each type, a row with two blocks is \(A^nB^n\) or \(B^nA^n\), already satisfying the requirement. Hence \(r\geqslant4\).

The subsequent operations cyclically rotate these \(r\) blocks without changing their lengths. Every block therefore becomes the last block at some stage. If its length is \(\ell\), its positions when last are \[ 2n-\ell+1,\ldots,2n. \] For it to contain position \(k\), we must have \[ \ell\geqslant 2n-k+1. \] Thus every block has at least \(2n-k+1\) coins.

Because the blocks alternate and \(r\geqslant4\) is even, there are at least two aluminium blocks. Counting their coins gives \[ n\geqslant2(2n-k+1). \] But the assumed upper bound on \(k\) implies \(2k\leqslant3n+1\), so \[ 2(2n-k+1)=4n-2k+2\geqslant n+1. \] This yields \(n\geqslant n+1\), a contradiction.

Hence every initial ordering eventually satisfies the requirement throughout the stated range. This also includes \(n=1\), for which the requirement holds initially for both possible values of \(k\).

The solution was checked against the official IMO shortlist solutions.