Problem: The Bank of Oslo issues two types of coin: aluminum (denoted $A$) and bronze
(denoted $B$). Marianne has $n$ aluminum 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 \leq 2n$,
Gilberty repeatedly performs the following operation:
he identifies the longest chain containing the $k$\ts{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 \to BBBAAABA \to AAABBBBA \to BBBBAAAA \to \dotsb$.

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

Solution: Answer: $n \le k \le \left\lceil \frac 32 n \right\rceil$.

Call a maximal chain a \emph{block}.
Then the line can be described as a sequence of blocks: it's one of:
\begin{align*}
  \underbrace{A\dots A}_{e_1}
  \underbrace{B\dots B}_{e_2}
  \underbrace{A\dots A}_{e_3}
  \dots
  \underbrace{A\dots A}_{e_m} & \text{ for odd $m$} \\
  \underbrace{A\dots A}_{e_1}
  \underbrace{B\dots B}_{e_2}
  \underbrace{A\dots A}_{e_3}
  \dots
  \underbrace{B\dots B}_{e_m} & \text{ for even $m$}
\end{align*}
or the same thing with the roles of $A$ and $B$ flipped.

The main claim is the following:
\begin{claim*}
  The number $m$ of blocks will never increase after an operation.
  Moreover, it stays the same if and only if
  \begin{itemize}
    \ii $k \le e_1$; or
    \ii $m$ is even and $e_m \ge 2n+1-k$.
  \end{itemize}
\end{claim*}
\begin{proof}
  This is obvious, just run the operation and see!
\end{proof}

The problem asks for which values of $k$ we always reach $m=2$ eventually;
we already know that it's non-increasing.
We consider a few cases:
\begin{itemize}
  \ii If $k < n$, then any configuration with $e_1 = n-1$ will never change.
  \ii If $k > \left\lceil 3n/2 \right\rceil$,
  then take $m=4$ and $e_1 = e_2 = \left\lfloor n/2 \right\rfloor$
  and $e_3 = e_4 = \left\lceil n/2 \right\rceil$.
  This configuration retains $m=4$ always:
  the blocks simply rotate.

  \ii Conversely, suppose $k \ge n$ has the property that $m > 2$ stays fixed.
  If after the first three operations $m$ hasn't changed,
  then we must have $m \ge 4$ even, and $e_m, e_{m-1}, e_{m-2} \ge 2n+1 - k$.
  Now,
  \[ n \ge e_m + e_{m-2} \ge 2(2n+1-k) \implies k \ge \frac 32 n + 1 \]
  so this completes the proof.
\end{itemize}