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 3 of 5: If

k

lies strictly inside a chain, two chains merge

Previous step Next step

In plain words

Moving a middle chain to the front joins its two neighbouring same-type chains into one, so the total chain count can only fall.

B_1=[l',l-1],\quad B_2=[m+1,m']

Detailed analysis

Suppose $k$ lies inside a chain $[l,m]$ with $l>1$ and $m<2n$ (not the first or last chain). Removing $[l,m]$ to the front lets the chain $B_1=[l',l-1]$ just before it and the chain $B_2=[m+1,m']$ just after it become adjacent; since $B_1$ and $B_2$ have the same coin type, they merge into a single chain, so the total number of chains strictly decreases.