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 4 of 5: Show the chain count keeps dropping for

n\le k\le\lceil3n/2\rceil

Previous step Next step

n\le k\le\lceil3n/2\rceil\ \Rightarrow\ \text{chains keep merging until }2\text{ remain}

Detailed analysis

If $k$ falls in the first chain $[1,l]$ with $l\ge k\ge n$ , then $l=n$ exactly, which is already the desired conclusion. If instead $k$ falls in the last chain, a pigeonhole count shows that whenever there are at least $4$ chains, some chain has fewer than $2n-k+1$ coins and so cannot always contain the last position holding $k$ ; hence $k$ must eventually land inside an interior chain (triggering the merge of the previous step) or in a configuration of only $2$ or $3$ chains, and repeating this argument drives the chain count down to $2$ , at which point the leftmost $n$ coins share one type.