I claim our answer is $\boxed{n \leq k \leq \lceil \tfrac32n \rceil}$. Indeed, note that if $k < n$, we can choose the a sequence formed by a $n-1$ length A block followed by a $n$ length $B$ block and then an $A$: the sequence would be stuck in this state forever. If $k > \lceil \tfrac32n \rceil$, then consider the sequence formed by a length $\lfloor \tfrac{n}{2} \rfloor$ length A block followed by a $\lfloor \tfrac{n}{2} \rfloor$ length B block then a $\lceil \tfrac{n}{2} \rceil$ length A block and a $\lceil \tfrac{n}{2} \rceil$ length B block. Moves only cycle the blocks since positions $2n - \lfloor \tfrac{n}{2} \rceil + 1 = \lceil \tfrac32n \rceil + 1 \rightarrow 2n$ are always be occupied by the same letters, and we would still never reach our desired end state. Now otherwise, we claim we always arrive at the desired end state. Note that if $k \to 2n$ are all occupied by the same letter, then a move does not merge any blocks. However, if that is not the case, then by moving the block containing the $k$th item to the front, we merge the block before and after it, decreasing the total block count by $1$. Furthermore, it is impossible to get stuck in a stage where we keep getting $k \to 2n$ to be part of some large block, since such a block would require size $\leq 2n - k + 1$, and we cannot have a sequence of $\ldots ABA$ or $\ldots BAB$ blocks all that big since\[(2n - k + 1) + (2n - k + 1) = 4n - 2k + 2 > n,\]the total number of $A$s and $B$s. Hence, performing the sequence of moves steadily decreases the number of blocks since we cannot get caught in an undesirable equilibrium position before inevitably reaching our desired outcome: a state with the minimal possible number of blocks. $ \square$

Answer: all pairs $(n, k)$ satisfying $n \le k \le \lceil 3n/2 \rceil$. Solution. Any $k \le n-1$ does not work because $A^{n-1}B^nA$ is a fixed point of the operation. Any $k > \lceil 3n/2\rceil$ does not work because \begin{align*} A^{\lfloor n/2\rfloor}B^{\lfloor n/2\rfloor}A^{\lceil n/2\rceil}B^{\lceil n/2\rceil} & \rightarrow B^{\lceil n/2\rceil} A^{\lfloor n/2\rfloor}B^{\lfloor n/2\rfloor}A^{\lceil n/2\rceil}\\ & \rightarrow A^{\lceil n/2\rceil}B^{\lceil n/2\rceil}A^{\lfloor n/2\rfloor}B^{\lfloor n/2\rfloor}\\ & \rightarrow B^{\lfloor n/2\rfloor}A^{\lceil n/2\rceil}B^{\lceil n/2\rceil}A^{\lfloor n/2\rfloor}\\ & \rightarrow A^{\lfloor n/2\rfloor}B^{\lfloor n/2\rfloor}A^{\lceil n/2\rceil}B^{\lceil n/2\rceil} \end{align*}is a cycle. The following argument shows that any $k$ satisfying $n\le k \le \lceil 3n/2\rceil$ works. Consider the number of chains after each operation, which is always a positive integer. This number is nonincreasing, because an operation preserves the contiguity of each chain, so it must be eventually constant. Say the process is stable when the number of chains reaches its final value. When the process is stable, the $k^\text{th}$ coin always lies in either the leftmost or the rightmost chain, otherwise the operation would merge the two chains next to the chain containing the $k^\text{th}$ coin. If $k = n$, then this is only possible if the leftmost chain has length $n$, so $k = n$ works. If $n+1 \le k \le \lceil 3n/2\rceil$, then the $k^\text{th}$ coin must always lie in the rightmost chain. Therefore the process results in a cyclic shift of chains, and each chain must have length $\ge 2n+1-k > n/2$, because when it is rightmost chain, it must contain the $k^\text{th}$ coin. This means that there can be only one $A$ chain and only one $B$ chain. Therefore, all chains have $n$ coins, and this includes the leftmost chain. $\blacksquare$

The answer is all pairs $(k,n)$ for which $n \leq k \leq 2n - \lfloor n/2 \rfloor$. Other values of $k$ fail when we consider the initial ordering \[\underbrace{AA...AA}_kBB...BBAA...AA\]for $k < n$, as the ordering does not change after a move is applied, and \[\underbrace{AA...AA}_{\lfloor n/2 \rfloor}\underbrace{BB...BB}_{\lfloor n/2 \rfloor}\underbrace{AA...AA}_{\lceil n/2 \rceil}\underbrace{BB...BB}_{\lceil n/2 \rceil}\]for $k > 2n - \lfloor n/2 \rfloor$, as the four chains (all with less than $n$ coins) continues to cycle their positions. Notice that during each move, no chain is broken, but some two chains with the same type of coins may be joined together. We will show that, after some finite number of moves, the number of (maximum length) chains will decrease, until it eventually becomes only 2 chains. During the process, if the leftmost chain is moved then we already have $n$ leftmost coins of the same type (because the first $k$ coins are in the same chain). If a middle chain is moved, then the two chains next to it will join together after the move is applied, resulting in a decrease of number of chains. Thus, it suffices to prove that after some finite moves the leftmost or middle chain is moved. Assume otherwise, then after some point the rightmost chain is always moved and no two chains are joined together. There must be an even number of chains, otherwise the leftmost and rightmost chain has the same type and will be joined. Furthermore, every chain moves to the rightmost position at least once, so we know there are at least $2n - k + 1 \geq \lfloor n/2 \rfloor + 1$ coins in each chain. But then the total number of coins is at least $4(\lfloor n/2 \rfloor + 1) > 2n$, contradiction. Hence, we will end up in two chains, and now it is easy to see that the $n$ leftmost coins will be the same when the longer chain is moved to the left end.

My video solution: link

Ok but harder than P2. Answer is all pairs $(n, k)$ with $n \le k < \frac{3n}{2} + 1$. If $k \le n$ take $A^{n - 1}BA^n$ which never changes. If $k \ge \frac{3n}{2} + 1$ take $A^{\lfloor n/2 \rfloor}B^{\lfloor n/2 \rfloor}A^{\lceil n/2 \rceil}B^{\lceil n/2 \rceil}$ which will go through the sequence $$A^{\lfloor n/2 \rfloor}B^{\lfloor n/2 \rfloor}A^{\lceil n/2 \rceil}B^{\lceil n/2 \rceil} \to B^{\lceil n/2 \rceil}A^{\lfloor n/2 \rfloor}B^{\lfloor n/2 \rfloor}A^{\lceil n/2 \rceil} \to A^{\lceil n/2 \rceil}B^{\lceil n/2 \rceil}A^{\lfloor n/2 \rfloor}B^{\lfloor n/2 \rfloor} \to B^{\lfloor n/2 \rfloor}A^{\lceil n/2 \rceil}B^{\lceil n/2 \rceil}A^{\lfloor n/2 \rfloor}$$ And then loops. We now prove that all other $k$ work. For convenience we will always consider maximal chains only when we say chain. Now if $n \le k < \frac{3n}{2} + 1$ we will prove that as long as there are at least $3$ chains, the number of chains will eventually decrease, so it will eventually become $2$ at which point we are done. The basic observation is that the number of chains will always stay the same or decrease when we do an operation, and it will only stay the same when the $k$-th position belongs to the last chain, and the first and last chains use a different letter. Otherwise we will either merge the last chain with the first chain or merge the two chains adjacent to the one that contains the $k$-th position. Finally by the previous observation, any operation that doesn't reduce the number of chains merely moves the last chain to the start, cycling the rest, for example when $k = 9$ for $n = 5$ we have $A^4B^2A^1B^3 \to B^3A^4B^2A^1$. The number of chains must also be even to prevent merging the first and last chains, so there are at least $4$ of them. Therefore the smallest chain contains at most $\lfloor 2n/4 \rfloor = \lfloor n/2 \rfloor$ letters. If we continue cycling then at some point this chain will be at the end of the string, but it is too short to contain the $k$-th position, so at this point the $k$-th position is not in the rightmost chain and we will be forced to reduce the number of chains.

Answer: $n \leq k \leq n+\lceil \frac{n}{2} \rceil$ Proof: Case 1: $k<n$ $AAAABBBBBA$ clearly fails. Case 2: $k=n$ Call a block left block if it contains the leftmost coin, right block if it contains the rightmost coin, and center block otherwise. Observe that if we select a center block, the number of blocks will decrease at least one, so we can do so only finitely many times. After that, we always select left or right blocks, but a block containing $k$-th coin can't be right block, so it must be left block, so the $n$ leftmost coins are all the same. Case 3: $k=n+1$ The same as Case 2, but a block can't be left block, so it must be right block, so the $n$ rightmost coins are all the same. Case 4: $n+1 < k \leq n+\lceil \frac{n}{2} \rceil$ Similar to Case 3, after some time we always select right blocks. We claim that at that time, there are only two blocks left. Assume the contrary, the smallest block must have size at most $\lfloor \frac{n}{2} \rfloor$. Also, observe that the blocks are just shifting in cyclic order, so when the smallest block becomes the rightmost block, we will miss it (since $k \leq 2n-\lfloor \frac{n}{2} \rfloor$), contradiction! Case 5: $k > n+\lceil \frac{n}{2} \rceil$ $AAABBBAABB$ ($\lceil \frac{n}{2} \rceil$ $A$s, then $\lceil \frac{n}{2} \rceil$ $B$s, then $\lfloor \frac{n}{2} \rfloor$ $A$s, then $\lfloor \frac{n}{2} \rfloor$ $B$s) clearly fails.

Quote: The Bank of Oslo I'm flattered

So we have Bank of Oslo, Bank of Bath, and Bank of Cape Town.

Solution: I claim the answer is $n\leqslant k\leqslant \left\lceil \frac 32 n\right\rceil$. First it's easy to show why $k<n$ fails: you put $n-1$ coins of the same type at the leftmost. Next it's also trivial why $k>\left\lceil \frac 32 n\right\rceil$ fails: you will fall into a loop. Finally I will prove why $n\leqslant k\leqslant \left\lceil \frac 32 n\right\rceil$ works. Denote $C$ by the total number of chains in the row. Obviously, $C$ doesn't increase every time we perform an operation. Assume the contrary, i.e. the first $n$ coins keep being different. Therefore eventually we will have $C\geqslant 3$. We first try like this: $$BB\cdots BB\quad AA\cdots AA\quad BB\cdots BB$$ Since $k\geqslant n$, we must have some $B$ in the first pile above. Also, if we have $B$ in the third pile above, then $C$ strictly decreases which is a contradiction. Then we can reduce the piles into the following: $$BB\cdots BB\text{ (notice that this pile must end with B )}\quad AA\cdots AA$$ The number of $A$s in the second pile is no less than $\left \lfloor \frac n2 \right\rfloor +1$. After we operate those $A$s to the leftmost, and in order to make sure we can still operate on $B$s similarly, then the number of $B$s in the first pile must also be $\geqslant \left \lfloor \frac n2 \right\rfloor +1$. This will lead to the total number of coins $> n+1$, contradiction. $\blacksquare$

The answer is $n \leq k \leq \lceil \frac {3n}{2} \rceil$. To see $k \leq n-1$ is impossible, choose the sequence $AA...ABB...BA$, where the first block is of length $n-1$, the second has length $n+1$. $k > \lfloor {\frac {3n}{2}} \rfloor+1$ is impossible by choosing four blocks $AA...ABB...BAA...ABB...B$ each of length $\lfloor \frac{n}{2} \rfloor$ (if $n$ is odd, take two of the block to have length with 1 bigger), and note that the $k$-th coin is always in the last block, so the process is in a cycle and we will never reach the desired configuration. To prove the other $k$ work, we are to prove that we can always decrease the number of blocks. Suppose that from some moment onwards we can't decrease the number of blocks. Note that number of blocks either decreases by at least $1$ or stays the same, where the latter holds only if the $k$-th coin is in the first or the last block (otherwise we merge two monochromatic blocks), but it's not in the first as it has length less than $n$, so $k$-th coin is always in the last block. Hence every block will be last at some moment. To finish, note that there are at least $4$ blocks, otherwise the number of blocks can be decreased (for the case of $3$ blocks), so there is a block with length at most $\lfloor \frac{n}{2} \rfloor$ , so when this block becomes last, the $k$-th coin won't be in it, so we are done. Comment: The hardest thing, in my opinion, is to determine the answer for the case $k>n-1$, the ideas for the decreasing of the number of blocks and that the $k$-th coin will be eventually always in the last block are easy to come up with. To prevent the $k$-th coin being in some last block, this block should have minimal length, and the length of the shortest block is always ensured to be at most $\lfloor \frac{n}{2} \rfloor$.

I'm unsure if this is rigorous enough, but here's my solution

What about the special case ABABABABABABABAB... if you choose A?

My sketchy solution

djmathman wrote: Quote: The Bank of Oslo I'm flattered tell me you didn't write this problem too

The answer is $n \leq k \leq 2n - \lfloor \tfrac{n}{2} \rfloor$ for all pairs $(n,k).$ First we show $n \leq k.$ Simply consider the sequence $A^kB^{k+1}A.$ Since the longest chain containing the $k$th coin, in this case the $k$th $A$ is the first coin to the $k$th coin, after the process the sequence remains invariant. Thus $n \leq k.$ Consider the ``endpoints" of the longest chain containing the $k$th coin. Define the $a$th and $b$th coins the first and last coins in the longest chain containing the $k$th coin. Note if $a=1,$ the leftmost $n$ coins are already of the same type, since $b \geq n.$ Thus consider $a>1.$ When this occurs, if $b \leq 2n-1,$ then after every operation the number of chains decrease; since there exists coins $a-1$ and $b+1$ that are of same type, and after the process the chain of coins starting at $a$ and ending at $b$ are moved to the left, and the two chains containing the $a-1$th and $b+1$th coins combine to form one chain. Notice if $b = 2n$ there is no decrease, since the longest chain containing the $k$th coin will be moved to the left, but in this case since the last coin of the sequence is contained in the longest chain, there will not be a $b+1=2n+1$'th coin to combine with the $a-1$th coin to form one sequence, so the number of chains remains invariant. Notice when the process reaches this step the sequence becomes a sequence of $A^n$ and $B^n.$ Therefore, in order for there to be a decrease of chains, the longest chain containing the $2n$th coin must be less than length $2n-k+1.$ Thus there exist two cases. Either every chain has length $2n-k+1$ or more, or there exist chains that have length elss than $2n-k+1.$ Note if every chain in the sequence has length greater than or equal to $2n-k+1,$ then the number of chains will never decrease, since the longest chain containing the $k$th coin will always have length at least $2n-k+1.$ Notice on the contrary if there exists a chain with length less than length $2n-k+1,$ then the number of chains will eventually decrease. We consider two cases, either we have $2n-k+1 \leq \lfloor \tfrac{n}{2} \rfloor$ or $2n-k+1 > \lfloor \tfrac{n}{2} \rfloor.$ We translate the former case as $k >2n-\lfloor \tfrac{n}{2}\rfloor,$ we can consider the sequence $A^{\lfloor \tfrac{n}{2} \rfloor}B^{\lfloor \tfrac{n}{2} \rfloor}A^{\lceil \tfrac{n}{2} \rceil}B^{\lceil \tfrac{n}{2} \rceil},$ which fails to have the leftmost $n$ coins to be the same type, as last $\lceil \tfrac{n}{2} \rceil$ get moved to the left, and the process keeps cycling. Thus this case fails, and it remains to consider $2n-k+1 > \lfloor \tfrac{n}{2} \rfloor,$ or $k \leq 2n-\lfloor \tfrac{n}{2}\rfloor.$ For this case, if there exists two or more chains of the same coin, since there are $n$ of that coins type, at least one of the chains will be shorter than $\lfloor \tfrac{n}{2} \rfloor +1.$ Then, since $2n-k+1 > \lfloor \tfrac{n}{2} \rfloor,$ that chain will be shorter length than $2n-k+1.$ Since such chains will eventually reach the position where it is the longest chain that contains $k,$ because it is also length $2n-k+1,$ the number of chains will keep decreasing until the leftmost $n$ coins will all be of the same type.

channing421 wrote:

This writeup took over an hour to finish; way longer than I would like. I think the primary reason for this is because I included way too many details. I would really appreciate it if someone could tell me which parts of my solution aren't necessary. Thanks!

We note that at each step of the process the total number of blocks (non-strictly) decreases, until either we run into some scenario where the number of blocks constantly stays the same, or we win. We consider all the scenarios where the number of chains is invariant (Other than any winning scenario). Note that either $k$ always lands in the first chain, or it always lands in the last chain, as otherwise if it landed in some middle chain, the chains adjacent would merge, decreasing the number of blocks. Case 1:(Always first block): For any $k \leq n-1$, as we can simply start with $AA\cdots ABBB\cdots BAA\cdots A$, where the first chain of $A$'s has size $k$ and the remaining ones are the remainder, and we will stay like this continuously. Case 2: The only other scenario for infinite invariance of the number of blocks occurs if we always have $k$ within the range of the last chain and also that the last chain always has different elements from the first chain (otherwise these will also merge). Then there are the same number of chains containing $A$'s as those containing $B$'s. In order for this process to repeat infinitely we must remain in these conditions (as it is impossible to go to the case 1 state). Since the size of each blocks will stay constant if all the blocks remain constant, we must have that the size of each block is larger than $2n-k+1$, such that $k$ is always the last element after the current block is moved to the front. Since these blocks will rotate around, that is why we need all of that to have such a size, as they will all be ending chains. Since we need at least 2 $A$ chains and 2 $B$ chains(as otherwise we are forced to have 1 of each, which would be the winning case. Thus we lose if $$n \geq 2 ( 2n-k + 1) \implies k \geq 1 + \lfloor \frac{3n}{2} \rfloor$$. Thus the conditions when we win is $n \leq k \leq \lceil \frac{3n}{2} \rceil$. (Sorry, i think i wrote "block" instead of chain sometimes. Also, definitely a great p1)

The answer is $n\le k\le\lceil\tfrac{3}{2}n\rceil$. Clearly, if $k<n$, then $A^{n-1}B^nA$ fails. If $k>\lceil\tfrac{3}{2}n\rceil$, then $A^{\lfloor\tfrac{n}{2}\rfloor}B^{\lfloor\tfrac{n}{2}\rfloor}A^{\lceil\tfrac{n}{2}\rceil}B^{\lceil\tfrac{n}{2}\rceil}$ fails. Otherwise, consider the number of chains. This is nonincreasing since each time we move, we move an entire block. Thus, it eventually converges. At any point after converging, the $k$th coin belongs to a chain that reaches an edge. If $k=n$ we are done. Otherwise, suppose it converges at at least $4$ chains and $k>n$ then the $k$th coin always belongs to the rightmost chain. Each chain length is at least $2n-k+1>\tfrac{n}{2}$ so four chains is more than $2n$, contradiction.

Answer is $n \leq k \leq \lceil \frac{3}{2} n \rceil$. Notice if $k \geq \frac{3}{2} n + 1$ we can construct four blocks of size $\lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil, \lfloor \frac{n}{2} \rfloor$ and you lose. If $n \leq k < \frac{3}{2} n + 1$ then $k$ cannot always lie in the rightmost block if there are $\geq 4$ blocks, and if $k$ lies in the leftmost block then it's ggs. Thus under each operation the total number of blocks weakly decreases as a monovariant. If $n \geq 4$ then it eventually strictly decreases and if $n = 3$ it strictly decreases by parity, so it must eventually reach $2$ blocks if you assume contradiction. However, this is a contradiction since one of the two blocks has size $\geq n$, finishing. For any $k < n$ just make the leftmost $k$ blocks $A$ and the rest $B$ for contradiction.

Let ceil function denote as [], and floor as <>. Note that if k<n, a block of n-1 As, n-1 Bs, then one A and one B doesn't work. If k>n+[n/2], a block of n+[n/2] As then Bs, and then a block of n+<n/2> As then Bs, the sequence keeps rotating around which doesn't work. Suppose FTSOC this process is infinite with n\le k\le n+[n/2]. Note that the rightmost chain is moved iff it has length 2n-k+1\ge\lfloor n/2\rfloor +1, meaning there's at most two consecutive times where you move rightmost chain, implying there are an infinite amount of times that a chain in the middle is moved (if on the left, we're done since k\ge n). However, it's evident that moving a middle chain decreases the number of chains by at least 1, but this can't continue infinitely, contradiction.

Lower bound: Clearly if $k<n$ then take $k$ aluminums and $1$ bronze, then $1$ aluminum. This fails. Now suppose that at some point we perform the operation on a run which is not an "edge run." Then we have (WLOG the run is bronze): \[A...AB...BA...A\to B...BA...AA...A\]and this decreases the number of runs. Hence the only way to fail is to eventually have all moves performed on an edge run. If the edge run is the front run then $k<n$ (when $k=n$ then the problem holds). If the edge run is the final run then notice that the number of runs must be even. Hence it is at least $4$ (if it's $2$ we are done). Hence the fail occurs only if (and also if!) $4(2n-k+1)\le 2n$ or $2n-k+1\le \left\lfloor \frac{n}{2}\right\rfloor$ so \[k\ge 2n+1-\left \lfloor \frac{n}{2}\right\rfloor=\left\lceil \frac{3}{2}n\right\rceil+1\]hence the interval that works is $k\in \left[n,\left\lceil \frac{3}{2}n\right\rceil\right]$.

We claim that any pair $\boxed{(n, k) \text{ with } n \leq k \leq \left\lceil \frac{3n}{2} \right\rceil}$ works. Claim: $k < n - 1$ Proof. Assume otherwise and take the counter-example of $\underbrace{AA\dots A}_{n - 1 \text{ times}}\underbrace{BB\dots B}_{n \text{ times}}A$ which obviously fails. $\square$ Claim: $k > \left\lceil \frac{3n}{2} \right\rceil$ Proof. For even $n$ consider taking \[\underbrace{AA\dots A}_{\frac{n}{2} \text{ times}}\underbrace{BB \dots B}_{\frac{n}{2} \text{ times}}\underbrace{AA \dots A}_{\frac{n}{2} \text{ times}}\underbrace{BB \dots B}_{\frac{n}{2} \text{ times}}\]This clearly fails for $k \geq \frac{3n}{2} + 1$. For odd $n$ consider taking \[\underbrace{AA\dots A}_{\left\lceil \frac{n}{2} \right\rceil \text{ times}}\underbrace{BB \dots B}_{\left\lfloor \frac{n}{2} \right\rfloor \text{ times}}\underbrace{AA \dots A}_{\left\lfloor \frac{n}{2} \right\rfloor \text{ times}}\underbrace{BB \dots B}_{\left\lceil \frac{n}{2} \right\rceil \text{ times}}\]This also can be easily shown to fail for $k \leq \left\lceil \frac{3n}{2} \right\rceil + 1$. $\square$ Now it suffices to show that all $k \in \left[n, \left\lceil \frac{3n}{2} \right\rceil\right]$ work, for arbitrary $n$. Assume we have a string of $A$ and $B$ characters, and that there are no $n$ consecutive $A$ characters. Now to show that we will win, the key insights are, The maximal length of a string of $A$ characters, and similarly of $B$ characters, never decreases. The number of ``breaks" in the string, namely places where we toggle between $A$ and $B$ characters such as $\dots AB \dots$ will decrease each turn. The first bullet follows trivially. If the second bullet always holds we are done. Thus assume that we reach a state where they are always constant. However note that whenever the chain containing the $k$-th element is removed, say a $B$ chain, and appended to the front of the string, two seperate $A$ blocks combine, unless the $B$ string is the last string in the sequence. Namely, to ensure that the number of ``breaks" do not decrease in a turn we must have a string of the form, \[\underbrace{AA\dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \dots \underbrace{AA \dots A}_{c_{\ell - 1} \text{ times}} \underbrace{BB \dots B}_{c_\ell \text{ times}}\]However then from our bounds on $k$ we find that we must have at least $\left\lceil \frac{n}{2} \right\rceil + 1 \leq c_\ell$. Now in the next ``position" we find that we have, \[ \underbrace{BB \dots B}_{c_\ell \text{ times}} \underbrace{AA\dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \dots \underbrace{AA \dots A}_{c_{\ell - 1} \text{ times}} \ \]Now assuming that there are no reduction in the number of ``breakpoints" we find that $\left\lfloor \frac{n}{2} \right\rfloor + 1\leq c_{\ell-1}$. Thus for any $c_i$ we may show a similar bound. However this then implies $\ell < 4$ or that we only have $3$ main strings. Thus we have reduced the problem to, \[ \underbrace{AA \dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \underbrace{AA \dots A}_{c_3 \text{ times}} \]where each $c_i \geq \left\lceil \frac{n}{2} \right\rceil + 1$. However then it is obvious that upon the next turn the two blocks of $A$ combine, giving our desired state. $\blacksquare$

We claim that any pair $\boxed{(n, k) \text{ with } n \leq k \leq \left\lceil \frac{3n}{2} \right\rceil}$ works. Claim: $k < n - 1$ Proof. Assume otherwise and take the counter-example of $\underbrace{AA\dots A}_{n - 1 \text{ times}}\underbrace{BB\dots B}_{n \text{ times}}A$ which obviously fails. $\square$ Claim: $k > \left\lceil \frac{3n}{2} \right\rceil$ Proof. For even $n$ consider taking \[\underbrace{AA\dots A}_{\frac{n}{2} \text{ times}}\underbrace{BB \dots B}_{\frac{n}{2} \text{ times}}\underbrace{AA \dots A}_{\frac{n}{2} \text{ times}}\underbrace{BB \dots B}_{\frac{n}{2} \text{ times}}\]This clearly fails for $k \geq \frac{3n}{2} + 1$. For odd $n$ consider taking \[\underbrace{AA\dots A}_{\left\lceil \frac{n}{2} \right\rceil \text{ times}}\underbrace{BB \dots B}_{\left\lfloor \frac{n}{2} \right\rfloor \text{ times}}\underbrace{AA \dots A}_{\left\lfloor \frac{n}{2} \right\rfloor \text{ times}}\underbrace{BB \dots B}_{\left\lceil \frac{n}{2} \right\rceil \text{ times}}\]This also can be easily shown to fail for $k \leq \left\lceil \frac{3n}{2} \right\rceil + 1$. $\square$ Now it suffices to show that all $k \in \left[n, \left\lceil \frac{3n}{2} \right\rceil\right]$ work, for arbitrary $n$. Assume we have a string of $A$ and $B$ characters, and that there are no $n$ consecutive $A$ characters. Now to show that we will win, the key insights are, The maximal length of a string of $A$ characters, and similarly of $B$ characters, never decreases. The number of ``breaks" in the string, namely places where we toggle between $A$ and $B$ characters such as $\dots AB \dots$ will decrease each turn. The first bullet follows trivially. If the second bullet always holds we are done. Thus assume that we reach a state where they are always constant. However note that whenever the chain containing the $k$-th element is removed, say a $B$ chain, and appended to the front of the string, two seperate $A$ blocks combine, unless the $B$ string is the last string in the sequence. Namely, to ensure that the number of ``breaks" do not decrease in a turn we must have a string of the form, \[\underbrace{AA\dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \dots \underbrace{AA \dots A}_{c_{\ell - 1} \text{ times}} \underbrace{BB \dots B}_{c_\ell \text{ times}}\]However then from our bounds on $k$ we find that we must have at least $\left\lceil \frac{n}{2} \right\rceil + 1 \leq c_\ell$. Now in the next ``position" we find that we have, \[ \underbrace{BB \dots B}_{c_\ell \text{ times}} \underbrace{AA\dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \dots \underbrace{AA \dots A}_{c_{\ell - 1} \text{ times}} \ \]Now assuming that there are no reduction in the number of ``breakpoints" we find that $\left\lfloor \frac{n}{2} \right\rfloor \leq c_{\ell-1}$. Thus for any $c_i$ we may show a similar bound. However this then implies $\ell < 4$ or that we only have $3$ main strings. Thus we have reduced the problem to, \[ \underbrace{AA \dots A}_{c_1 \text{ times}} \underbrace{BB \dots B}_{c_2 \text{ times}} \underbrace{AA \dots A}_{c_3 \text{ times}} \]where each $c_i \geq \left\lfloor \frac{n}{2} \right\rfloor$. However then it is obvious that upon the next turn the two blocks of $A$ combine, giving our desired state. $\blacksquare$

The answer is pairs $(n,k)$ for which $n \leq k \leq \lceil \tfrac{3n}{2} \rceil$. Firstly, consider a chain $X$ surrounded by two other chains (i.e. not the leftmost or rightmost chain). If we shift $X$ to the front, the two chains that formerly surrounded it now merge into one, decreasing the total number of chains. Now, we split into cases: If $k \leq n-1$, consider the position of $n-1$ aluminum coins followed by $n$ bronze coins followed by $1$ bronze coin. Then, repeating this process does nothing, so $k > n-1$. If $k = n$, the longest chain containing the $k$th coin is either the first $n$ coins, or it is surrounded by two other chains. In the former case, we have attained the desired position; otherwise, repeating the process will, as stated, decrease the total number of chains until there are only two chains left. If $n+1 \leq k \leq \lceil \tfrac{3n}{2} \rceil$, our process will always shift a chain which has a neighbor on the left. At some point the total number of chains must stop decreasing, which means from that point on we will always be shifting a chain which has no neighbor to its right. By then, we will be in an endless loop of replacing the sequence of coins with a cyclic permutation of itself. Because $k \leq \lceil \tfrac{3n}{2} \rceil$, each chain in our cycle will have a length of at least $\lfloor \tfrac{n}{2} \rfloor + 1$. Since $4 \cdot \left( \lfloor \tfrac{n}{2} \rfloor + 1 \right) > n$, we must have at most $3$ chains in our sequence. If we have $3$ chains, our next move will decrease our number of chains to $2$. And if we have $2$ chains, we are in the desired position. If $k \geq \lceil \tfrac{3n}{2} \rceil + 1$, then we set the first $\lfloor \tfrac{n}{2} \rfloor$ coins to be aluminum, the next $\lfloor \tfrac{n}{2} \rfloor$ coins to be bronze, the next $\lceil \tfrac{n}{2} \rceil$ coins to be aluminum and the remaining $\lceil \tfrac{n}{2} \rceil$ coins to be bronze. This will leave us repeatedly replacing the sequence of coins with a cyclic permutation of itself.

We claim the answer is all $n$ and $k\in[n,\lfloor 3n/2\rfloor]$. Let $a_1,a_2,\dots,a_{\ell}$ denote $a_1$ amber, $a_2$ bronze, $a_3$ amber, and so on. For the lower bound, consider $n-1,n,1$ suffices. For the upper bound, $\lfloor n/2\rfloor, \lceil n/2 \rceil,\lceil n/2 \rceil,\lfloor n/2\rfloor$ suffices. Assume FTSOC that $k\in[n,\lfloor 3n/2\rfloor]$ and we never finish. Note that the number of chains is strictly decreasing unless we move an end group and we have at least $4$ groups. If we are moving the first group, its size must be at least $k\ge n$ at which point we are already done. Hence, we must move the end group infinite times. For this to happen, each group must have size at least $2n-k+1$ and with at least $4$ groups we have $2n\ge 4(2n-k+1)\implies n\ge 3k/2+1$ which is absurd. $\square$

The answer is $\boxed{n\leq k\leq \lceil\frac{3n}{2}\rceil}$. Construction: Notice that the number of consecutive blocks of coins is non-increasing. If it never reaches $2$ there must be some point where it is constant. Notice all the blocks will eventually be in the $k^{th}$ position. But then every block containing the $k^{th}$ coin must contain the last coin so each block has size larger than $\frac{n}{2}$, a contradiction. Bound: If $k<n$ just take $AA\dots ABB\dots BA$. If $\lceil\frac{3n}{2}\rceil<k$ then take $AA\dots ABB\dots BAA\dots A BB\dots B$ with the number of each coin type in each consecutive group differing by at most $1$.

Claim: The answer is all pairs with $n\leq k\leq\lceil\tfrac{3}{2}n\rceil$. Proof: We give examples for $k<n$ and $k>\lceil\tfrac{3}{2}n\rceil$: $\underbrace{A\dots A}_{n-1}\underbrace{B\dots B}_{n}A$ $\underbrace{A\dots A}_{\lfloor\frac{n}{2}\rfloor}\underbrace{B\dots B}_{\lfloor\frac{n}{2}\rfloor}\underbrace{A\dots A}_{\lceil\frac{n}{2}\rceil}\underbrace{B\dots B}_{\lceil\frac{n}{2}\rceil}$ $\bullet$ In the first example $k<n$ and clearly the configuration isn't even going to change. $\bullet$ In the second example $k>\lceil\tfrac{3}{2}n\rceil$ and that's so that the chains are going to cycle. Now we consider $n\leq k\leq\lceil\tfrac{3}{2}n\rceil$. First let $\lambda$ be the chain we pick and suppose it's not the leftmost one. That way, when we move $\lambda$, its adjacent chains will merge and the total amount of chains will decrease.

of chains does not change. As $k>n$ we will always move a chain, and we know it has to be the rightmost one. Let $X_1, X_2,\dots, X_m$ be the chains, in that order, and $x_1, x_2,\dots, x_m$ be the amount of coins in each one of them. As we showed the chains are going to cycle, thus: $\begin{cases} x_1+\dots+x_{m-1}\leq k-1 \\ x_m+\dots+x_{m-2}\leq k-1 \\ \dots \\ x_2+\dots+x_{m}\leq k-1 \end{cases}$ $\Rightarrow (m-1)\underbrace{(x_1+\dots+x_m)}_{2n}\leq m(k-1)\Rightarrow$ $\Rightarrow m(2n-k+1)\leq 2n\Rightarrow \frac{2n}{2n-k+1}\geq m\geq 4\Rightarrow 8n-4k+4\leq 2n\Rightarrow$ $\Rightarrow k\geq\tfrac{3}{2}n+1>\lceil\tfrac{3}{2}n\rceil$, Contradiction! That means we are done .

This didn't take me much time but I initially forgot the upper bound which I quickly corrected. We claim that the answer is all pairs $(n,k)$ for which $n \le k \le \lceil {\frac{3n}{2}}\rceil$. We start off with some definitions. We We call the $k^{th}$ coin, in the row for our chosen $k$ the move coin. Further, the first (left-most) chain is called the leading chain while the last (right-most) chain is called the trailing chain. The chain containing the move coin is called the move chain. We say a chain is $A$-type if it contains $A$ coins and $B$-type if it contains $B$ coins. We first show that all other $k$ fail. If $k<n$, we simply consider the coin placement, \[\underbrace{A\dots A}_{n-1}\underbrace{B\dots B}_{n}A\]and if $k>\lceil\tfrac{3}{2}n\rceil$ we consider the coin placement, \[\underbrace{A\dots A}_{\lfloor\frac{n}{2}\rfloor}\underbrace{B\dots B}_{\lfloor\frac{n}{2}\rfloor}\underbrace{A\dots A}_{\lceil\frac{n}{2}\rceil}\underbrace{B\dots B}_{\lceil\frac{n}{2}\rceil}\] The first does not work since it is clearly fixed under the given move, and the second doesnt work since $n-k < \lfloor\frac{n}{2}\rfloor$, so the $k^{\text{th}}$ coin will be in the trailing chain in all moves, thus we cycle forever moving the 4 chains, to the left-most position repeatedly. Now, we consider $n \le k \le \lceil {\frac{3n}{2}}\rceil$. We let $T$ denote the number of chains in our configuration of coins in a given moment. It is immediately clear that $T$ is non-increasing since in each move, we are simply choosing a complete chain, and moving it to the left-most position so no new chains are created. If the move chain, is neither the leading chain, nor the move chain then after a move $T$ decreases by 2 if the leading chain is of the same type as the move chain (since then the chains either side of the move chain become one chain and the move chain joins up to the leading chain), and decreases by 1 if the move chain is of a different type to the leading chain. Now, it is clear that the move chain is not the leading chain since if $k>n$ then that chain itself would contain more than $n$ coins of the same type and if $k=n$ then we would in fact be done. Further, if the move chain is the trailing chain, we simply pick up the move chain and move it to the front until we obtain a move chain which is not trailing. This must eventually happen since $k < \lceil {\frac{3n}{2}}\rceil$ implies that $n-k > \lfloor {\frac{n}{2}}\rfloor$. But, there must exist some chain of length less than $\lfloor {\frac{n}{2}}\rfloor$ since the length of all chains sum to $2n$ and we must have atleast 4 chains for obvious reasons (2 chains is already done and 3 chains is done in the first move). Thus, whenever we meet such a chain we reduce $T$ and keep going, reducing $T$ until we eventually reach $T=2$ at which point we must be in our desired configuration.

This is a really good problem. Sadly, it is trivial by small cases.

Wow, this is super nice The answer is all $k$ such that $\boxed{k \le \left\lceil \frac{3n}{2} \right\rceil}.$ Claim: If $k \ge \left\lceil \frac{3n}{2} \right \rceil,$ then the problem is not satisfied. Proof: Consider the string $$A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor}A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor},$$where the subscript indicates the length of the chain. Notice that it cycles $$A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor}A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor} \rightarrow B_{\lfloor\frac{n}{2}\rfloor}A_{\lceil\frac{n}{2}\rceil }B_{\lfloor\frac{n}{2}\rfloor}A_{\lceil\frac{n}{2}\rceil } \rightarrow A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor}A_{\lceil\frac{n}{2}\rceil}B_{\lfloor \frac{n}{2}\rfloor},$$and thus it must continue to cycle. Claim: It suffices to show that, if $k \le \lfloor \frac{3n}{2}\rfloor,$ we must eventually decrease the number of chains. Proof: Notice that, if we show this, then at any point, we know that the number of chains must decrease in a finite number of turns, which obviously implies that we must eventually get two chains. Claim: If $k \le \lfloor \frac{3n}{2}\rfloor,$ we must eventually decrease the number of chains. Proof: Let the sequence of chains be $A_{i_{1}}B_{i_{1}}\dots A_{i_{k}}.$ Notice that if the $k$-th coin from the left is not the last chain (WLOG assume that it is $B_{i}$), then the chains next to the chain which the $k$-th coin is in merge, as they are the same letter. Thus, we assume that the $k$-th coin from the left is in the last chain, or that the last chain has length at least $2n-k+1.$ In fact, as we cycle through all the chains being the last one, it becomes evident that we may assume that all of the chains have this length. So, there are at most $$\left\lfloor \frac{n}{2n-k+1} \right\rfloor \le \left \lfloor \frac{n}{ 2n-\left\lceil \frac{3n}{2}\right\rceil+1}\right\rfloor = \left\lfloor \frac{n}{\lfloor \frac{n}{2} \rfloor +1} \right\rfloor \le 3 ,$$so the number of chains is $3.$ Thus, the sequence is of the form $A_{i}B_{j}A_{k}$ or $B_{i}A_{j}B_{k}.$ But, when we move the last chain to the back, the first two chains merge, and thus we are done.

The answer is all pairs satisfying $\boxed{n \leq k \leq \left \lceil \frac{3n}{2} \right \rceil}$. Call a string of consecutive letters a block if they are all the same letter and the two (or one) letters adjacent to it are different. The idea of this problem is that the number of blocks never decreases, hence the bad cases occur when the number of blocks stay the same and cycle around. Claim: All $k < n$ fail. Proof: Consider the first $n-1$ coins being of one color, the next $n$ being different, and the last coin being of the same color as the first. The sequence would never change. $\blacksquare$ Claim: All $k > \left \lceil \frac{3n}{2} \right \rceil$ fail. Proof: For this case, the counterexample will be sort of like an assembly line, with the blocks cycling forever. If $n$ is even, consider four blocks of length $\frac{n}{2}$. If $n$ is odd, consider two blocks of length $\frac{n+1}{2}$ followed by two blocks of length $\frac{n-1}{2}$. $\blacksquare$ It remains to show that all $k$ within the range satisfy the conditions. We have reached a desired configuration when there is only two blocks. Because of the lower bound we can safely say that the selected block is not the first one (else we are already done). The number of blocks will strictly decrease if the selected block is not the last. If it is the last, it would still strictly decrease if the first and last coin are the same color. In other words, the number of blocks is forever the same (i.e. the bad cases) when at every iteration we select the last block which has a different color than the first. We claim this is impossible for $k$ within this range. If we really kept cycling infinetly, we clearly must have an even number of chains greater than two. The ending chain (and hence ALL chains, because we are cycling) must contain the $k$th coin and hence have length at least $2n-k+1$. But because of our upper bound on $k$ all chains are at least $\left \lfloor \frac{n}{2} \right \rfloor + 1$. However, $4(\left \lfloor \frac{n}{2} \right \rfloor + 1) > 2n$, so this is impossible. Hence we are done.