Ideas on this hard problem?

WRONG SOLUTION. Solved if it was "the minimum $i$" instead of the maximum. We will prove the following statement by induction on $n$. Claim. R. L. can make exactly $n!$ moves. Also, after these moves, the string is the same as the initial string, but reversed. Proof: it's easy to check this for $n = 1, 2, 3$. Assume the statement holds for $n$. Now, let our string be $s_1s_2 \ldots s_{n+1} $. Due to induction hypothesis, R. L. makes $n!$ operations, after which the string is $s_n \ldots s_1 s_{n+1}$. Now, the next operation must be flipping the whole string. Thus, the new string is $s_{n+1}s_1s_2\ldots s_n$. Now, we have our last character being $s_n$. Therefore, we can again do $n!$ operations for the first $n$ characters of the string and always get new strings. After this, our string is $s_{n-1}s_{n-2} \ldots s_2s_1s_{n+1}s_n$. Again, reverse the whole string. We get $s_n s_{n+1} s_1 s_2 \ldots s_{n-2} s_{n-1}$. And once again, we have a new character at the end of the string. It's not difficult to prove by another induction what's going on: After $k\cdot n! + 1$ operations (when writing the string out is counted as the first move), our string is $s_{n+2-k}s_{n+3-k}\ldots s_{n+1} s_1 s_2 \ldots s_{n+1-k}$. And after this, there's $n!$ operations on the first $n$ characters. We also see, that after $(n+1)!$ operations, our string is $s_{n+1}s_n \ldots s_1$, which was to be proved. Thus, the induction hypothesis holds for $n+1$. Q.E.D.

Loppukilpailija wrote: Claim. R. L. can make exactly $n!$ moves. Also, after these moves, the string is the same as the initial string, but reversed.. Actually this is wrong On the very second move, R.L. should produce a string which is the same as the initial string, but reversed..

Oh, my mistake. I read the problem statement as "the minimum $i$", and not "the maximum $i$".

This feels well-known though I've never seen it before; nice problem though We'll prove the statement by induction on $n$ with base cases trivial. Let $a_1a_2...a_n$ be the initial word. We'll define a shift of word $b_1b_2...b_n$ to be the word $b_2b_3...b_nb_1$. Let the sequence of words R.L. writes be $w_1,w_2,...,w_m$; we'd like to show $m=n!$. Also let $\overline{w}$ be $w$ in reverse order. Lemma 1: $w_{2k} = \overline{w_{2k-1}}$ for all $k$. Proof: We induct on $k$ with base case obvious. For the inductive step, suppose $w_{2k}\neq \overline{w_{2k-1}}$. Then since flipping $i=n$ moves is maximal, the only possible explanation is that $\overline{w_{2k-1}}$ occured somewhere in the sequence before $w_{2k-1}$. But if $\overline{w_{2k-1}}$ occurs before $w_{2k-1}$, it must occur directly beforehand, hence $w_{2k-2} = \overline{w_{2k-1}}$, so by the inductive hypothesis we know $w_{2k-2} = \overline{w_{2k-3}} \implies w_{2k-1}=w_{2k-3}$, contradiction, and we're done. Lemma 2: Each word in the sequence $w_{2kn+1}, w_{2kn+3}, ..., w_{2kn + (2n-1)}$ after the first one is a shift of the previous word in that sequence for all $k$. Proof: We induct on $k$. The key idea is that reversing all letters of a word, followed by reversing the first $n-1$ letters of that word, results in a shift. Indeed, for the base case it's not hard to verify that for all $i$, we have $a_{2i-1} = a_ia_{i+1}...a_na_1a_2...a_{i-1}, a_{2i} =\overline{a_{2i-1}}$ for $i=1,2,...,n$. Now suppose we've shown the result for $k$ and would like to show it for $k+1$. By the inductive hypothesis coupled with lemma 1, we know that each of the tuples $(w_{2ln+1}, w_{2ln+3}, ..., w_{2ln+(2n-1)})$ along with $(w_{2ln+2}, w_{2ln+4}, ..., w_{2ln+2n})$ is closed under shifting for $l\le k$. Therefore, all the iterative shifts of $w_{2(k+1)n+1}$ and $\overline{w_{2(k+1)n+2}}$ have never been written before. Then it follows that, after writing $w_{2(k+1)n+1}$, R.L. will alternate between reversing $n$ letters of the word and reversing the first $n-1$ letters- this is obviously optimal, and it always produces previously unwritten words due to our observation about reversing $n$ and then $n-1$ letters being equivalent to a shift. Lemma 3: For all $k$, $w_{2kn+1}, w_{2kn+2n}$ both end in $a_n$. Furthermore, words not of this form do not end in $a_n$. Proof: We again induct on $k$ with base case $k=0$ trivial. For the inductive hypothesis, note that by lemma 1 we cannot have $w_{2(k+1)n+1} = \overline{w_{2kn+2n}}$. Therefore, $w_{2(k+1)n+1}$ is written by reversing the first $i$ letters of $w_{2kn+2n}$ for some $i<n$, implying that $a_n$ keeps its position at the end of the word. Then by lemmas 1,2 again it's not hard to show that $w_{2(k+1)n+2n}$ will also end in $a_n$. Then using lemma 2, we can easily see that words not of this form must by iterative shifts of words ending in $a_n$, so they cannot themselves end in $a_n$. Now we are ready to prove the problem statement by induction on $n$. Assume for $n-1$ that we have the sequence $v_1,v_2,..., v_{(n-1)!}$ of words built with the letters $a_1,a_2,...,a_{n-1}$. Now we'll consider $w_1,w_2,...,$. I claim that the sequence formed by putting all the $w_{2kn+1}, w_{2kn+2n}$'s in order of occurrence is exactly the sequence $v_1, v_2, ..., v_{(n-1)!}$ where each $v_i$ has an $a_n$ appended to the end. Indeed, we'll prove by induction on $k$ that $w_{2(k-1)n+1} = v_{2k-1}a_n, w_{2(k-1)n+2n} = v_{2k}a_n$ by induction on $k$ with base case $k=1$ obvious. We saw earlier that $w_{2kn+1}$ must come from reversing the first $i<n$ letters of $w_{2(k-1)n+2n} = v_{2k}a_n$. Since $a_n$ stays in place, when we try to reverse the first $i<n$ letters of $v_{2k}a_n$, the only words we have to worry about repeating are words of the form $w_{2(l-1)n+1}, w_{2(l-1)n+2n} = v_{2l-1}a_n, v_{2l}a_n$ by the inductive hypothesis. Then this is equivalent to reversing the first $i<n$ letters of $v_{2k}$ in a way which does not repeat a word from the set $\{v_1,v_2,..., v_{2k-1}\}$, so by the inductive hypothesis the result we end up with is precisely $v_{2k+1}$, hence $w_{2kn+1} = v_{2k+1}a_n$. Now using lemmas 1,2 we can easily prove $v_{2kn+2} = v_{2k+2}a_n$ and fill in the words in between, so the inductive step is complete and we have generated a new sequence of words of length $n!$.

I think it is same this problem https://artofproblemsolving.com/community/c6h1343800p7308405

Can anyone give me an example of such a string because im not able to understand it.

Quote: I think it is same this problem That was CMO2016 P4 and trivial by induction...... It was even called the easiest P4 in 5 years. So perhaps this one should be a little harder? Though I haven't found any actual differences.