Nice problem regarding arrows

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 $a \leftarrow bc \leftarrow d$ in a text editor (where $\leftarrow$ denotes the left-arrow key of the keyboard), you get the string $bdca$. Hence, we can insert arrows within string $abcd$ in such a way that we get the string $bdca.$

Now, consider two strings $A$ and $B$ . Suppose that you can insert arrows within string $A$ to obtain string $B.$ Show that you can also insert arrows within string $B$ to obtain string $A.$

Just to clarify, you are allowed to enter multiple arrows before a character. For example, doing $ab \leftarrow \leftarrow cd$ (which gives the string $cdba$ ) is allowed. However, you cannot use right arrows.

Here's an example which shows this for the strings $abcd$ and $bcda$ :

As already shown above, we can insert arrows within $abcd$ to obtain $bcda$ . We shall show that we can insert arrows within $bcda$ to obtain $abcd.$ This is simple; just do $bcd \leftarrow \leftarrow \leftarrow a.$

Also, just to be specific, we're working with strings of any length, not just length $4$ , 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 $\{1, 2, \cdots , n\}$ to be attainable from a permutation of $\{1, 2, \cdots , n\},$ 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. :)

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

wlog take the initial string $S_n$ as composed of the integer i at each index i. For example, instead of 'abcd' in your example we would call it '1234'. Now, any string obtained from S consists of a permutation on (1, 2, ... n). Call this $a_1, a_2, ... a_n$ . What strings can NOT be obtained? It is easy to see that the strings which cannot be obtained are precisely those for which we can find three indices i < j < k such that $a_j < a_i < a_k$ . But in this case we can take $a_i, a_j, a_k$ as $i, j, k$ in the operation to see that the inverse of the permutation also satisfies this condition. In other words, if a permutation cannot be obtained from $S_n$ , then neither can its inverse. Therefore, if a permutation CAN be obtained then so can its inverse.

ww margera - 6 years, 9 months ago

Yup, that's precisely my solution. Just filling out the details; here's the solution I wrote in the AoPS thread.

WLOG let string $A$ be $1, 2, \cdots , n,$ so $B$ is a permutation of $1, 2, \cdots , n.$ Let's characterize all permutations from which $A$ is reachable. Consider a permutation $b_1, b_2, \cdots , b_n$ of $1, 2, \cdots , n$ from which $A$ can be reached.

Define an increasing block starting from $b_i$ to be a subset of $\{b_1, b_2, \cdots , b_n\}$ of the form $\{b_i, b_{i+1}, \cdots , b_{i+j}\},$ where $b_{i+k} > b_{i+k-1}$ for all $1 \leq k \leq j.$ Also, define the associate of $b_i$ to be the largest $b_j$ satisfying $j<i$ and $b_j<b_i.$

Note that to transform $b_1, b_2, \cdots , b_n$ into $1, 2, \cdots , n,$ we must add arrows according to the following rules.

Start with $b_1.$ Let $S_1$ be the largest increasing block starting from $b_1.$ Let $b_j$ be the last element of $S_1$ . Add a suitable number of arrows to the left of $b_{j+1}$ such that $b_{j+1}$ gets placed just to the right of its associate.
Let $b_i$ be the element our cursor is currently on. Do the basically same thing with $b_i$ : let $S_i$ be the largest increasing block starting from $b_i.$ Add arrows at the end of its last element so that the element after it gets placed right after its associate.
Keep doing this throughout the whole sequence.

(Just to clarify, the string $b_1, b_2, \cdots , b_n$ gets modified after each step accordingly.)

This is the only way we can transform $\{b_i\}_{i=1}^{n}$ to $\{i\}_{i=1}^{n}.$ To see why this is true, note that after arrows have been placed to the left of some $b_i,$ its position can't be changed later, so we must make sure that each element has been placed just to the right of the largest operated element smaller than it (operated in the sense that arrows have been placed to the right of it so its position can't be changed anymore).

Now, this algorithm fails precisely when there exists an $i$ such that the largest increasing block starting from $b_i$ contains an element $b_j$ which is larger than at least one of the elements between $b_k$ and $b_{i-1},$ where $k$ denotes the position where $b_j$ gets placed after shifting the largest increasing block starting from $b_i$ to the left. If such a $i$ doesn't exist, the largest block starting from $1$ increases in length every time a number is shifted towards the left. Eventually, this block has length $n.$ This is when we have the string $1, 2, \cdots , n.$ If such a $i$ exists, we have a number whose position can't be changed anymore larger than a number to the right of it whose position can't be changed either, so we can't reach $1, 2, \cdots , n.$

The existence of such an $i$ is equivalent to the existence of some positive $x, y, z$ satisfying $b_{x+y} < b_{x} < b_{x+y+z}.$ Let's call all permutations for which there exist such $x, y, z$ good.

Claim: If a permutation is good, so is its inverse. Proof: Let $\{\sigma (i)\}_{i=1}^{n}$ be a good permutation of $\{i\}_{i=1}^{n},$ and let $\{\varphi (i)\}_{i=1}^{n}$ be the inverse of $\sigma,$ so $\varphi (\sigma (i))= i$ for all $i.$ Now, there exist $x, y, z$ such that $\sigma(x+y) < \sigma (x) < \sigma (x+y+z).$ But, we also have that $\varphi (\sigma (x+y+z)) > \varphi (\sigma (x+y) ) > \varphi (\sigma (x)),$ so taking $(x_2, x_2+y_2, x_2+y_2+z_2) = (\sigma (x+y) , \sigma (x), \sigma(x+y+z))$ does the job. $\blacksquare$

Using the lemma, it follows that if $\{i\}_{i=1}^{n}$ can be reached from $\{b_i\}_{i=1}^{n},$ $\{b_i\}_{i=1}^{n}$ can be reached from $\{i\}_{i=1}^{n}.$ This shows that if $A$ can be reached from $B,$ $B$ can be reached from $A,$ completing the proof. $\blacksquare$

I'm well aware that my proof above is a very badly phrased one; sorry if some parts of it are very vague / hard to understand. I'll be glad to add clarifications to certain unclear parts in my solution if someone asks.

There also exists a nice solution using induction which my friend found. I can post it here if necessary. I'm looking for other's solutions here too!

Sreejato Bhattacharya - 6 years, 9 months ago

That is very interesting

Mezhona Gray - 6 years, 8 months ago

Let String = ab Now we can say that ab,ba (only two possible permutations using left arrows) both can be converted back to ab So we know this property holds true for n=2 Now take a string of length n, A1A2A3A4A5....An where Ai stand for a character i - integer Lets suppose the property holds true for string of length n Now lets prove it for string of length n+1 String S= A1A2A3A4A5....AnA(n+1) Now lets suppose We obtain string k. String k will of of the form 2. k = AiAj....ApA(n+1)........AqAr

If the string is in the first form we can consider AnA(n+1) to be a single character and this is similar to string n.

For second form Consider string X= AiAj....Ap.......AqAr (remove A(n+1) from string K) We can easily say that String X can be obtained from String Y = A1A2A3.....An as K is derived from S... (I can comment on this if any one finds the above statment difficult to understand)

From the assumption, we know String X can also be derived from Y.... Now we know (AiAj<-<-.....)Ap(..An...Ar) = A1A2A3...An The above ... denotes some set of Operations... So I want to denote them by O1 and O2

O1ApO2 = A1A2...An

Now for String K O1ApA(n+1)<-O2 will yield the result A1A2....AnA(n+1)

So we can prove that if this property holds for n then it also holds for n+1

Hence proved!!!!!

I am really bad at writing solutions..... I am not at all accustomed for this formatting and all......So please let me know if

Siddhartha Devapujula - 6 years, 8 months ago

Is each letter in the string considered distinct?

Daniel Liu - 6 years, 9 months ago

Yes.

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$