International Mathematical Olympiad

Define a block to be a maximal subsequence of consecutive coins made out of the same metal, and let $M^b$ denote a block of $b$ coins of metal $M$. The property that there is at most one aluminium coin adjacent to a copper coin is clearly equivalent to the configuration having two blocks, one consisting of all $A$-s and one consisting of all $C$-s.

First, notice that if $k<n$, the sequence $A^{n-1}{C}^{n-1}AC$ remains fixed under the operation, and will therefore always have 4 blocks. Next, if $k>\frac{3n+1}{2}$, let $a=k-n-1$, $b=2n-k+1$. Then $k>2a+b$, $k>2b+a$, so the configuration $A^a{C}^b{A}^b{C}^a$ will always have four blocks: $$A^a{C}^b{A}^b{C}^a\to C^a{A}^a{C}^b{A}^b\to A^b{C}^a{A}^a{C}^b\to C^b{A}^b{C}^a{A}^a\to A^a{C}^b{A}^b{C}^a\to \dots$$ Therefore a pair $(n,k)$ can have the desired property only if $n⩽k⩽\frac{3n+1}{2}$. We claim that all such pairs in fact do have the desired property. Clearly, the number of blocks in a configuration cannot increase, so whenever the operation is applied, it either decreases or remains constant. We show that unless there are only two blocks, after a finite amount of steps the number of blocks will decrease.

Consider an arbitrary configuration with $c⩾3$ blocks. We note that as $k⩾n$, the leftmost block cannot be moved, because in this case all $n$ coins of one type are in the leftmost block, meaning there are only two blocks. If a block which is not the leftmost or rightmost block is moved, its neighbor blocks will be merged, causing the number of blocks to decrease.

Hence the only case in which the number of blocks does not decrease in the next step is if the rightmost block is moved. If $c$ is odd, the leftmost and the rightmost blocks are made of the same metal, so this would merge two blocks. Hence $c⩾4$ must be even. Suppose there is a configuration of $c$ blocks with the $i$-th block having size $a_i$ so that the operation always moves the rightmost block: $$A^{a_1}\dots A^{a_{c-1}}{C}^{a_c}\to C^{a_c}{A}^{a_1}\dots A^{a_{c-1}}\to A^{a_{c-1}}{C}^{a_c}{A}^{a_1}\dots C^{a_{c-2}}\to \dots$$ Because the rightmost block is always moved, $k⩾2n+1-a_i$ for all $i$. Because $\sum a_i=2n$, summing this over all $i$ we get $ck⩾2cn+c-\sum a_i=2cn+c-2n$, so $k⩾2n+1-\frac{2n}{c}⩾\frac{3n}{2}+1$. But this contradicts $k⩽\frac{3n+1}{2}$. Hence at some point the operation will not move the rightmost block, meaning that the number of blocks will decrease, as desired.