USAMO 2017 -TSTST P2: Which words can Ana pick?

Question

Ana and Banana are playing a game. First Ana picks a word, which is defined to be a nonempty sequence of capital English letters. (The word does not need to be a valid English word.) Then Banana picks a nonnegative integer $k$ and challenges Ana to supply a word with exactly $k$ subsequences which are equal to Ana's word. Ana wins if she is able to supply such a word, otherwise she loses.

For example, if Ana picks the word "TST", and Banana chooses $k=4$, then Ana can supply the word "TSTST" which has $4$ subsequences which are equal to Ana's word.

Which words can Ana pick so that she wins no matter what value of $k$ Banana chooses? (Find all words such that Ana can pick at the start and always have a winning response regardless of the value of $k$ chosen by Banana.)

Remarks.

If Ana chooses "A", then for any $k$, Ana can give a word with exactly $k$ subsequences "AAA...A" ($k$ times). If Ana chooses "AB", then for any $k$, Ana can give a word with exactly $k$ subsequences "ABBB...B" ($k$ times).

If Ana chooses a string with no repetition at the end, say $X_1X_2X_3\cdots X_n$, where $X_{n-1}\neq X_n$, then Ana wins for any value of $k$ by supplying $$X_1X_2X_3\cdots X_{n-1}\underbrace{X_nX_n\cdots X_n}_{k\text{ terms}}\,.$$

If Ana chooses a string of length $n>1$ consisting of the same letter, she loses if Banana takes $k=2$ already.

PS: I didn't posted it AOPS since we only get solutions there .

Thanks in advance.

Answer 1

Hint (as requested by the OP). In combination with my last comment under your question, show that every word $X_1X_2\ldots X_n$ Ana can use to always win must have a letter that is not the same as its neighbors (from both sides). Prove also that, if this condition is not met, Banana wins with $k=2$.

Warning! If you do not wish to see the whole solution, do not move your mouse over the hidden portion below. A solution sketch is given there.

If Ana chooses the word $X_1X_2\ldots X_n$ such that, for some $i=1,2,\ldots,n$, $X_i$ is different from both neighbors, then for any positive integer $k$, Ana wins by responding with $$X_1X_2\cdots X_{i-1}\underbrace{X_iX_i\cdots X_iX_i}_{k\text{ times}}X_{i+1}\cdots X_{n-1}X_n\,.$$ For the other direction, suppose that Ana chooses a word $X_1X_2\cdots X_n$ such that, for every index $i$, either $X_i=X_{i-1}$ or $X_i=X_{i+1}$. Banana responds by picking $k=2$.
We shall prove that any string $Y_1Y_2\cdots Y_m$ that contains at least two copies of $X_1X_2\cdots X_n$ as a substring must contain more than $2$ copies of $X_1X_2\cdots X_n$. For $i=1,2,\ldots,n$, let $a_i$ denote the smallest index $j\in \{1,2,\ldots,m\}$ such that there exists a substring of $Y_1Y_2\ldots Y_m$ where $X_i$ is taken from the position $Y_j$. We also let $b_i$ to be the largest index $j\in\{1,2,\ldots,m\}$ such that there exists a substring of $Y_1Y_2\ldots Y_m$ where $X_i$ is taken from the position $Y_j$.
Divide $X_1X_2\ldots X_n$ into $Z_1Z_2\cdots Z_r$, where each cluster $Z_s$ is a sequence of the same letter such that consecutive clusters $Z_s$ and $Z_{s+1}$ do not share a letter. Define $z_s$ and $z'_s$ to be the first and the last positions of the letters in $Z_s$ (i.e., their positions in $X_1X_2\cdots X_n$). Show that, for some $s=1,2,\ldots,r$, there are at least $z'_s-z_s+2$ indices $\ell$ such that $a_{z_s}\leq \ell\leq b_{z'_s}$ and $Y_\ell=X_{z_s}$. Therefore, there are at least $$\binom{{z'_s}-{z_s}+2}{z'_s-z_s+1}\geq z'_s-z_s+2\geq 3$$ substrings of $Y_1Y_2\cdots Y_m$ that equal $X_1X_2\cdots X_n$.