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\le2n

, 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. Find all pairs

(n,k)

with

1\le k\le2n

such that for every initial ordering, at some moment during the process, the leftmost

n

coins will all be of the same type.

Step 1 of 5: Rule out

k<n

with a frozen arrangement

Previous step Next step

In plain words

If $k$ is small, an arrangement can keep the $k$ -th coin permanently inside a chain too short to ever reach the left end fully.

A\ldots A\,B\ldots B\,A

Detailed analysis

For $k<n$ , take the initial arrangement $A\ldots A\,B\ldots B\,A$ (a block of $A$ 's, then all $n$ of the $B$ 's, then one final $A$ ), chosen so the $k$ -th coin always lies inside the long leading $A$ -chain; performing the operation moves that same chain to the front and the arrangement is unchanged, so the leftmost $n$ coins are never monochromatic.