MathDB

A sequence of

X

s and

O

s is given, such that no three consecutive characters in the sequence are all the same, and let

N

be the number of characters in this sequence. Maia may swap two consecutive characters in the sequence. After each swap, any consecutive block of three or more of the same character will be erased (if there are multiple consecutive blocks of three or more characters after a swap, then they will be erased at the same time), until there are no more consecutive blocks of three or more of the same character. For example, if the original sequence were

XXOOXOXO

and Maia swaps the fifth and sixth character, the end result will be

XXOOOXXO \to XXXXO \to O.

Find the maximum value

N

for which Maia can’t necessarily erase all the characters after a series of swaps. Partial credit will be awarded for correct proofs of lower and upper bounds on

N

Problem Statement