Hi everyone! I recently came across this nice problem, and decided to share it here for others to enjoy. Feel free to post your thoughts and solutions!
When you write the string in a text editor (where denotes the left-arrow key of the keyboard), you get the string . Hence, we can insert arrows within string in such a way that we get the string
Now, consider two strings and . Suppose that you can insert arrows within string to obtain string Show that you can also insert arrows within string to obtain string
Just to clarify, you are allowed to enter multiple arrows before a character. For example, doing (which gives the string ) is allowed. However, you cannot use right arrows.
Here's an example which shows this for the strings and :
As already shown above, we can insert arrows within to obtain . We shall show that we can insert arrows within to obtain This is simple; just do
Also, just to be specific, we're working with strings of any length, not just length , and all characters of the strings are distinct (thanks Daniel).
Source: USA TSTST 2014
This is one of my favorite problems. I've given this to many of my friends (mostly people who qualified RMO but unfortunately failed INMO), and we've gotten many different solutions to this problem. I have a solution which finds a condition for the string to be attainable from a permutation of and then shows that if this condition holds for a permutation, it must also hold for its inverse, completing the proof (I can post it if necessary). A friend of mine has another nicer solution using induction, I can also post that for him if anyone wants.
I'm looking forward to how the people here approach this really nice problem. Thanks for reading this. :)