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 5 of 5: State the final answer

Previous step Next step

(n,k):\ n\le k\le\lceil3n/2\rceil

Detailed analysis

Combining the two impossibility constructions with the merging argument, the pairs that always succeed are exactly those with $n\le k\le\lceil3n/2\rceil$ .