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 2 of 5: Rule out

k>\lceil3n/2\rceil

with a four-chain cycle

Previous step Next step

\lfloor n/2\rfloor,\ \lceil n/2\rceil,\ \lceil n/2\rceil,\ \lfloor n/2\rfloor

Detailed analysis

For $k>\lceil3n/2\rceil$ , take four chains of sizes $\lfloor n/2\rfloor,\lceil n/2\rceil,\lceil n/2\rceil,\lfloor n/2\rfloor$ alternating $A,B,A,B$ ; since the last chain has at least $\lfloor n/2\rfloor$ coins, $k$ always falls inside it, and moving it to the front simply rotates the four chains, so the pattern repeats forever without ever producing $n$ matching leftmost coins.