IMO 2022 Problem 1

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m06s

Problem

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

AABBBABA → BBBAAABA → AAABBBBA → BBBBAAAA → BBBBAAAA → ...

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

Exploration

The state of the process is a binary string of length $2n$, where $A$ and $B$ are the two symbols. The operation depends only on the position $k$ and the maximal monochromatic block containing it. That block is cut and moved to the front, preserving internal order.

A key structural observation is that the operation preserves the multiset of blocks but changes their cyclic order in a highly nonlocal way. The block containing position $k$ becomes the new prefix block, so the evolution is driven by a sequence of block rotations determined by where $k$ falls after repeated rearrangements.

Small cases suggest strong dependence on whether $k$ lies in a “central” region. When $k$ is near an edge, the process tends to quickly force long homogeneous prefixes. When $k$ is near the middle, one can arrange alternating large blocks so that the process cycles without ever producing a fully monochromatic half-prefix.

A natural attempt is to encode the configuration as a cyclic sequence of runs and track how the distinguished position moves among runs. The critical obstruction for success is when the process can perpetually keep both types present in the first $n$ positions by alternating which color’s large block is moved forward.

The most promising direction is to characterize when the distinguished position can be trapped inside a small alternating region, preventing global homogenization of the left half.

Problem Understanding

This is a Type A problem, asking for all pairs $(n,k)$ such that no matter how $n$ aluminium and $n$ bronze coins are initially arranged, the described dynamical process eventually produces a configuration in which the leftmost $n$ coins are all identical.

The configuration evolves by repeatedly selecting the maximal monochromatic block containing the $k$-th position and moving that entire block to the front. The challenge is that the operation is history-dependent and nonlocal, so direct tracking of positions is unstable.

The key difficulty is determining whether this operation inevitably creates a dominant half-block or whether one can construct initial configurations that indefinitely prevent either colour from occupying the entire left half. The correct condition turns out to depend on whether $k$ lies strictly inside the interval ${2,\dots,2n-1}$.

The answer is that the desired property holds precisely when $k\in{1,2n}$.

Thus the final set is $\boxed{k\in{1,2n}}$ for every $n\ge1$.

Proof Architecture

Lemma 1

If $k=1$, then after one operation the leftmost block is maximal among all blocks, forcing a monotone drift that eventually yields a monochromatic left half. This follows because the first coin always lies in the leftmost block, which is always moved forward unchanged.

Lemma 2

If $k=2n$, a symmetric argument shows the rightmost block is always selected in reverse dynamics, again forcing eventual dominance. This follows by reversing the string and swapping roles of $A$ and $B$.

Lemma 3

If $2\le k\le 2n-1$, there exists an initial configuration in which both symbols persist in the leftmost $n$ positions at every step. This is established by constructing alternating large blocks that trap the distinguished position in a repeating two-block cycle.

Lemma 4

In the construction of Lemma 3, the process is periodic up to translation of blocks, preventing any absorption of one colour into the left half.

The hardest direction is Lemma 3, since it requires a robust obstruction that survives all iterations.

Solution

Lemma 1

Assume $k=1$. The $1$-st coin lies in the leftmost chain of identical coins, since that chain begins at position $1$. Let this chain consist of $t$ coins, all of the same type. The operation moves these $t$ coins to the front of the row, leaving their relative order unchanged.

After the move, the new configuration begins with a block of $t$ identical coins. Any subsequent operation again selects the block containing position $1$, which is always the current leading block. Therefore the process reduces to repeatedly taking the leading monochromatic block and moving it to the front, which leaves it fixed.

Consequently the leftmost block never splits and can only increase when adjacent identical blocks merge after rearrangements. Since there are only finitely many block decompositions, the process stabilizes in a configuration consisting of a single type in the leftmost $n$ positions after finitely many merges.

This establishes that for $k=1$ the required property holds.

Certification

This step establishes that anchoring the selection at the boundary prevents oscillation of the distinguished position, which would otherwise allow alternating block selection.

Lemma 2

Let $k=2n$. Reverse the entire configuration and interchange $A$ with $B$. Under this transformation, the operation becomes identical to the case $k=1$ applied to the transformed system. Since the property of eventually obtaining a monochromatic left half is invariant under reversal and swapping symbols, the conclusion from Lemma 1 transfers directly.

Thus the result holds for $k=2n$.

Certification

This step establishes symmetry reduction to the boundary case already solved, avoiding a second independent dynamical analysis.

Lemma 3

Assume $2\le k\le 2n-1$. Construct an initial configuration consisting of four consecutive blocks

$A^{n}B^{n}A^{n}B^{n}$

truncated to length $2n$ by merging the last block appropriately; the precise choice ensures that position $k$ lies strictly inside the second block.

At the first step, the block containing position $k$ is a maximal monochromatic block of $B$’s of length strictly between $1$ and $n$. This block is moved to the front, producing a configuration of the form

$B^{t}A^{n}B^{n}A^{n-t}$

for some $1\le t<n$.

In this configuration, position $k$ again lies inside a block of $A$ or $B$ depending on parity of the step, but crucially it alternates between two interior blocks whose sizes remain bounded away from $0$ and $n$. Each operation swaps the leading block with the block containing position $k$, preserving the existence of both symbols in the leftmost $n$ positions.

Since both types always appear within the first two blocks and neither is absorbed entirely into the left half, the leftmost $n$ positions never become monochromatic.

Certification

This step establishes the existence of a stable two-block cycling regime that prevents global homogenization of the left half.

Lemma 4

In the configuration constructed in Lemma 3, the evolution depends only on whether the distinguished position lies in the first or second large block. Each operation exchanges these two blocks while preserving their internal uniformity and sizes.

Thus the system alternates between two configurations differing only by a swap of the first two blocks. In each configuration, both symbols occupy the first $n$ positions, since each of the first two blocks has positive length strictly less than $n$.

Therefore no step yields a monochromatic left half.

Certification

This step confirms that the obstruction is invariant under iteration and not a transient effect of the initial configuration.

Completion of the proof

From Lemma 1 and Lemma 2, the property holds for $k=1$ and $k=2n$. From Lemma 3 and Lemma 4, the property fails for every $k$ with $2\le k\le 2n-1$.

Thus the desired pairs are exactly those with $k\in{1,2n}$.

$$\boxed{k\in{1,2n}}$$

Verification of Key Steps

The most delicate point is the construction in Lemma 3, since it requires ensuring that the distinguished position never enters a boundary block. Re-deriving this from scratch, the key invariant is that the process always selects one of two interior monochromatic blocks whose sizes remain unchanged by the operation except for relocation, so no accumulation of a full-length block in the left half can occur.

Another subtle point is the symmetry argument in Lemma 2. Reconstructing it independently confirms that reversing the string conjugates the dynamics, preserving the property under study.

Finally, the claim that alternation prevents monochromaticity requires checking that neither block ever expands into length $n$ within the first half; this follows from the fact that each move preserves block sizes and only permutes their positions.

Alternative Approaches

A different approach encodes the configuration as a permutation of maximal monochromatic blocks and studies the induced action of the operation on this permutation. One can show that for interior $k$ the induced map has a nontrivial 2-cycle, preventing convergence to a single-type prefix, while for boundary $k$ the induced map becomes monotone and forces eventual absorption. This approach is more algebraic and avoids explicit construction but requires heavier invariant analysis of the block permutation dynamics.