A word is initially written with n different letters. Then at each step you write a new word of n letters, reversing the longest initial subword that does not produces a word of $n$ letters already written in the previous steps. Prove that we will write $n!$ words.
It is from an Italian IMO TST for IMO of 2019.
For example let $123$ a world, it become:
- $321$
- $231$
- $132$
- $312$
- $213$
- $123$
I think that induction work. The base case is 2 and work, let $1,2$ the two letters: $(1,2) $ become $(2,1)$ and we have $2!$ words. If it is true for $n$, i want prove it is also for $n+1$ I think to make a n-tuple the is the mutual position of the number less then $n+1$. For example if $n=4$ the word 23541 has the 4-tuple $(2,3,4,1)$. I think that it can help with induction (because we have now n letter). We now must understan how change the n-tuple when we change the n+1 word reversing the letter according to the hypothesis of the problem. I have made no progress from here. I hope it can be solved by induction, but it is also possible that it cannot. I'd really appreciate a solution with induction, but I'd appreciate any solution. Thanks.